Accueil et informations générales

Myriam PREISSMANN (INP Grenoble - CNRS)
Hyperchemins hamiltoniens

Un tournoi est un graphe complet orienté. Par le théorème de Rédei on sait que tout tournoi possède un chemin hamiltonien. Nous avons étudié une généralisation de ce problème aux hypergraphes orientés qui peut s'exprimer de la manière suivante.
Un hypertournoi est un graphe complet dont les arêtes sont coloriées et orientées de sorte que : pour chaque couleur, le graphe induit par l'ensemble des arcs de cette couleur est un graphe biparti complet, et tous les arcs sont orientés de l'un des côtés de la bipartition vers l'autre côté. La conjecture est que "Tout hypertournoi contient un chemin hamiltonien dont les arcs ont chacun une couleur différente." On utilise un théorème de Graham-Pollak Tverberg et le théorème d'intersection de deux matroides d'Edmonds, pour montrer un théorème plus faible dans la direction de cette conjecture.
Collaboration avec Jenö Lehel, Emmanuel Preissmann, András Sebö.

Emeric GIOAN (Université Montpellier 2 - CNRS)
Polynôme de Tutte et énumérations d'orientations

L'activité d'une région d'un arrangement d'hyperplans indique sa position par rapport à la suite de faces emboîtées induite par la base minimale. En termes de matroïdes orientés (ou de graphes), les activités d'une orientation comptent le nombre d'éléments minimaux dans les circuits/cocircuits positifs (ou cycles/cocyles orientés).
Les coefficients du polynôme de Tutte permettent de compter les régions/orientations d'activités données, et sont invariants vis à vis de l'ordre des éléments.
Une conjecture prétend que le nombre de bases est toujours plus petit que le nombre d'orientations acycliques (régions) ou que le nombre d'orientations totalement cycliques (régions du dual). Cette conjecture peut être raffinée à différents niveaux, en termes de convexité du polynôme de Tutte, de comparaison entre coefficients de ce polynôme, et d'interprétations géométriques.

Pause

Jorge RAMÍREZ ALFONSÍN (Université Montpellier 2)
Multi-décompositions du polytope des bases d'un matroïde

Une décomposition du polytope des bases, P(M), d’un matroïde M est une subdivision de P(M) en polytopes P(Mi) telle que (a) P(Mi) est également un polytope des bases d’un matroïde pour un certain matroïde Mi, et (b) l’intersection de P(Mi) et P(Mj) est une face de P(Mi) et de P(Mj).
Dans cet exposé, nous présenterons de résultats concernant de décompositions en plusieurs polytopes.
Nous donnons des conditions suffisantes sur M pour que P(M) puisse avoir une multi-décomposition.

Déjeuner

Arnau PADROL (Universitat Politècnica de Catalunya, Espagne)
Many neighborly polytopes and oriented matroids

We say that a d-polytope P is neighborly if every subset of at most d/2 vertices is a face of P. This concept applies naturally to oriented matroids. We present a new construction that allows to extend balanced oriented matroids. In the dual setting, this means that given a neighborly oriented matroid of rank d with n elements, we obtain a new neighborly oriented matroid of rank d+1 with n+1 elements.
With this construction we can generate many non-realizable neighborly matroids and prove that the number of different neighborly d-polytopes with n vertices is at least of order n^(nd/2) when n>2d, which even improves previously known lower bounds for the number of different combinatorial types of polytopes.

Daria STEPANOVA (Université Montpellier 2)
Géométrie tropicale des Delta-matroïdes

Dans cet exposé je présenterai les nouvelles avancées de la théorie des Delta-matroïdes pairs sous le point de vue tropical. En suivant "Isotropical linear spaces and valuated Delta-matroids" de F. Rincón, on peut considérer un Delta-matroïde pair valué comme un vecteur de Wick tropical. Cette considération nous a donné l'idée de tropicaliser d'autres notions physiques et algébriques comme par exemple l'algèbre de Wick. Je donnerai une brève description combinatoire de ce procédé.

Victor CHEPOI (Université d'Aix-Marseille)
Bucolic complexes

In this talk, we introduce and investigate bucolic complexes,a common generalization of systolic complexes and of CAT(0) cubical complexes. This class of complexes is closed under Cartesian products and amalgamations over some convex subcomplexes. We study various approaches to bucolic complexes: from graph-theoretic and topological viewpoints, as well as from the point of view of geometric group theory. Bucolic complexes can be defined as locally-finite simply connected prism complexes satisfying some local combinatorial conditions. We show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In particular, we prove a version of the Cartan-Hadamard theorem, the fixed point theorem for finite group actions, and establish some results on groups acting geometrically on such complexes. We also characterize the 1-skeletons (which we call bucolic graphs) and the 2-skeletons of bucolic complexes. In particular, we prove that bucolic graphs are precisely retracts of Cartesian products of locally finite weakly bridged graphs (i.e., of 1-skeletons of weakly systolic complexes). We show that bucolic graphs are exactly the weakly modular graphs satisfying some local conditions formulated in terms of forbidden induced subgraphs and that finite bucolic graphs can be obtained by gated amalgamations of products of weakly bridged graphs.
Join work with B. Bresar, J. Chalopin, T. Gologranc, and D. Osajda.

Michel POCCHIOLA (Université Pierre et Marie Curie)
Sur l'axiomatisation des arrangements de double pseudodroites

Un arrangement de double pseudodroites est une famille finie de courbes simples fermées triviales du plan projectif réel s'intersectant deux-à-deux en quatre points d'intersections transverses et induisant deux-à-deux une décomposition cellulaire du plan projectif. Les familles duales des familles finies de corps convexes disjoints deux-à-deux des géométries projectives réelles bidimensionnelles sont des examples d'arrangements de double pseudodroites. Inversement tout arrangement de double pseudodroites est isomorphe à la famille duale d'une famille finie de corps convexes disjoints deux-à-deux d'une géométrie projective réelle bidimensionnelle. Dans cet exposé je discuterai d'un système d'axiomes de la classe des arrangements de double pseudodroites dont chaque axiome porte sur au plus cinq double pseudodroites et dont le nombre d'axiomes est petit en regard du nombre d'arrangements d'au plus cinq double pseudodroites.

Olivier DURAND DE GEVIGNEY (INP Grenoble)
Packing de sous graphe-rigides et d'arbres couvrants

Nous montrons que tout graphe simple (6p+2q,2q)-connexe contient p sous-graphes rigides et q arbres couvrants arête-disjoints. Ce résultat unifie deux extensions du résultat classique de Lovász et Yemini qui stipule que les graphes 6-connexes sont rigides. Il permet aussi d'améliorer deux bornes sur la connexité des graphes ayant des propriétés particulières : (1) tout graphe 8-connexe contient un arbre couvrant et un sous-graphe couvrant 2-connexe arête-disjoints; (2) tout graphe 14-connexe admet une orientation 2-sommet-connexe. La preuve de ce résultat utilise l'union de p matroïdes de rigidité et de q matroïdes graphiques.
Travail en commun avec Joseph Cheriyan et Zoltán Szigeti.

Pause

András SEBÖ (INP Grenoble - CNRS)
Sous-graphes avec contraintes de parité et de connectivité

Etant donne des poids non-négatifs, un sous-graphe de poids minimum avec des contraintes de parité des degrés, ou, de poids minimum et connexe, peut-être déterminé en temps polynomial. Le minimum est caractérisé par de jolis théorèmes minimax classiques. Et si on demande les deux types de contraintes ensemble ? Si on demande les deux ensemble on arrive à un problème qui contient la détection d'un circuit Hamiltonien d'un graphe. Dans cet exposé je montre la solution d'un cas particulier via le théorème de l'intersection de deux matroides (Edmonds) ou des systèmes de représentation par des forêts (Lovász). Ceci est un résultat commun avec Jens Vygen et constitue le coeur matroïdal de notre travail de 7/5-approximation pour le problème du voyageur de commerce graphique.

Bilan (discussion projet TEOMATRO)