Graphe de Levi

À partir d'un ensemble de points et de droites dans une géométrie d'incidence ou une configuration géométrique, on forme un graphe avec un sommet par point, un sommet par droite et une arête pour chaque incidence entre un point et une droite. Ces graphes sont nommés d'après Friedrich Wilhelm Levi, qui les a décrit dans des publications en 1942[1] - [3].

Le graphe de Levi d'un système de points et de droites a généralement une maille au moins égal à six : un cycle de longueur 4 correspond à deux droites passant par les mêmes points. Inversement, tout graphe bipartite avec une maille d'au moins six peut être considéré comme le graphe de Levi d'une structure d'incidence abstraite. Les graphes de Levi des configurations sont biréguliers, et chaque graphe birégulier avec de maille de six ou plus peut être vu comme le graphe de Levi d'une configuration abstraite[4].

Des graphes de Levi peuvent également être définis pour d'autres types de structures d'incidence, tels que les incidences entre les points et les plans dans l'espace euclidien. Pour chaque graphe de Levi, il existe un hypergraphe équivalent, et vice versa.

• Le graphe de Desargues est le graphe de Levi de la configuration de Desargues, composée de 10 points et 10 droites. Il y a 3 points sur chaque droite et 3 droites passant par chaque point. Le graphe de Desargues peut également être vu comme le graphe de Petersen généralisé G(10,3) ou le graphe de Kneser biparti avec les paramètres 5,2. Il est 3-régulier et a 20 sommets.
• Le graphe de Heawood est le graphe de Levi du plan de Fano. Il est également connue sous le nom de (3,6)-cage, et est 3-régulier et a 14 sommets.
• Le graphe de Möbius-Kantor est le graphe de Levi de la configuration de Möbius-Kantor, un système de 8 points et 8 droites qui ne peut pas être réalisé par des droites géométriques dans le plan euclidien. Il est 3-régulier et a 16 sommets.
• Le graphe de Pappus est le graphe Levi de la configuration de Pappus, composé de 9 points et 9 droites. Comme la configuration Desargues, il y a 3 points sur chaque droite et 3 droites passant par chaque point. Il est 3-régulier et a 18 sommets.
• 

  configuration de Gray.
  Le graphe de Gray est le graphe de Levi d'une configuration réalisable en ${\displaystyle \mathbb {R} ^{3}}$ comme une grille de 27 points et des 27 droites orthogonales qui les traversent.
• Le graphe de Tutte-Coxeter est le graphe de Levi de la configuration de Cremona-Richmond (en). C'est une (3,8)-cage ; il est 3-régulier et possède 30 sommets.
• Le graphe de l'hypercube en quatre dimensions ${\displaystyle Q_{4}}$ est le graphe de Levi de la configuration de Möbius formée par les points et les plans de deux tétraèdres mutuellement incidents.
• Le graphe de Ljubljana sur 112 sommets est le graphe de Levi de la configuration de Ljubljana[5].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Levi graph » (voir la liste des auteurs).

• (en) Eric W. Weisstein, « Levi Graph », sur MathWorld