Notes of Victor Chepoi’s july 2013 lecture

Graphes de bases de matroides

On va établir un mécanisme analogue à la caractérisation des complexes cubiques {CAT(0)} : il suffit de vérifier une condition locale (sur les liens) et la simple connexité.

Curiosité : Maurer, Isbell, Nash ont eu le meme directeur de thèse, Albert Tucker.

1. Matroides

1.1. Trois définitions équivalentes d’un matroide

Un matroide, c’est un complexe simplicial fini qui satisfait l’axiome d’échange : Si {I} et {I'} sont des simplexes, avec {|I'|>|I|}, alors il existe {e\in I'\setminus I} tel que {I\cup\{e\}} est un simplexe.

Exemple : les ensembles de vecteurs linéairement indépendants.

Je vais utiliser une autre axiomatique, celle des bases. Une base d’un matroide, c’est un simplexe maximal. L’axiome d’échange entraine que toutes les bases ont le meme cardinal. Donc, dans cette version de la définition, on se donne un ensemble de bases, qui satisfait

Si {B},{B'} sont deux bases, alors pour tout {e\in B'\setminus B}, il existe {e'\in B\setminus B'} tel que {B\setminus\{e\}\cup \{e'\}} est une base.

Troisième définition possible : les circuits. Les circuits sont les ensembles dépendants minimaux. Ils sont sujets à 3 axiomes

  1. {\emptyset} n’est pas un circuit.
  2. minimalité.
  3. pour toute arete commune à deux circuits, il existe un circuit contenu dans la réunion qui évite cette arete.

1.2. Le graphe des bases

Les sommets correspondent aux bases. Une arete relie deux bases {B} et {B'} dès que {|B\Delta B'|=2}.

C’est le 1-squelette du polyèdre du matroide, enveloppe convexe des vecteurs colonnes de la matrice d’incidence élément/base.

Conjecture (Mihail, Sudan). Les graphes des bases des matroides forment un expanseur, avec constante de Cheeger égale à 1 : si l’ensemble des sommets est partitionné en {S} et {S'}, alors

\displaystyle  \begin{array}{rcl}  E(S,S')\geq \min\{|S|,|S'|\}. \end{array}

1.3. Caractérisation des graphes des bases

Question (Maurer). Quels graphes apparaissent comme graphes des bases de matroides ?

Voici les conditions nécessaires recensées par Maurer en 1973.

  1. Les graphes de bases sont connexes (plus, ils se plongent dans des hypersimplexes).
  2. Condition d’intervalles : si {d(B,B')=2}, alors {B} et {B'} appartiennent à un carré, une pyramide à base carrée ou un octaèdre.
  3. Condition du lien : soit {B} une base. Les bases à distance 1 de {B} forment le graphe d’incidence des aretes d’un graphe biparti.
  4. Condition du positionnement : soit {B} une base, on s’intéresse à la fonction distance à {B}, et à ses restrictions possibles à un carré. Il y a 3 configurations possibles : constante, prend 2 valeurs (constante sur deux cotés), prend 3 valeurs (constante sur exactement une diagonale).

Theorem 1 (Maurer 1973) {G} est le graphe des bases d’un matroide si et seulement il satisfait ces 4 propriétés.

Maurer était jeune et optimiste, il a conjecturé que certaines conditions ne sont pas indispensables. Dès 1977, un contre exemple a été trouvé à sa conjecture initiale.

Proposition 2 Soit {G} un graphe. On note {X(G)} le 2-complexe obtenu en remplissant les triangles et les carrés dans {G}. Si {G} est le graphe des bases d’un matroide, alors {X(G)} est simplement connexe.

Maurer a conjecturé que cette propriété pouvait remplacer l’une ou plusieurs des 4 précédentes.

2. Résultats

2.1. Caractérisation locale/globale des graphes des bases

Theorem 3 (Chalopin, Chepoi, Osajda) Pour un graphe {G}, les conditions suivantes sont équivalentes.

  1. {G} est le graphe des bases d’un matroide.
  2. {X(G)} est simplement connexe et toute boule de rayon 3 de {G} est comme une boule de rayon 3 d’un matroide.
  3. {X(G)} est simplement connexe, {G} satisfait la condition d’intervalles, la condition de positionnement locale (positionnement pour les carrés situés à distance {\leq 2}), et {G} possède un sommet de degré fini.

2.2. Preuve

Le plus intéressant, c’est {3.\Rightarrow 2.}. On s’appuie sur le théorème de Maurer : il faut vérifier la condition de lien et la condition de positionnement global. On le fait par récurrence sur les niveaux de la distance à un sommet, mais en reconstruisant les couches. La construction s’apparente à celle du revetement universel.

2.3. Questions

La condition de simple connexité est elle indispensable dans le théorème ? Oui. Sinon, il y a ce contre exemple de 1977.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s