Graphe de Levi

Graphe de Levi
Image illustrative de l’article Graphe de Levi
Le graphe de Pappus est un graphe de Levi à 18 sommets formé à partir de la configuration de Pappus. Les sommets marqués d'une seule lettre correspondent à des points de la configuration ; les sommets marqués de trois lettres correspondent à des droites passant par trois points.
Distribution des degrés birégulier
Maille ≥ 6
Propriétés graphe biparti
modifier 

En mathématiques, et plus particulièrement en combinatoire, un graphe de Levi ou graphe d'incidence est un graphe biparti associé à une structure d'incidence[1],[2].

Description

À 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.

Exemples

  • 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 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 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].

Notes et références

  1. ↑ a et b Branko Grünbaum, « Configurations of points and lines », dans The Coxeter Legacy, Providence, RI, American Mathematical Society, (MR 2209028, lire en ligne), p. 179–225.
  2. ↑ Burkard Polster, A Geometrical Picture Book, New York, Springer-Verlag, coll. « Universitext », (ISBN 0-387-98437-2, DOI 10.1007/978-1-4419-8526-2, MR 1640615, lire en ligne), p. 5.
  3. ↑ Friedrich Wilhelm Levi, Finite Geometrical Systems, Calcutta, University of Calcutta, , iii + 51 (MR 0006834).
  4. ↑ Harald Gropp, « VI.7 Configurations », dans Charles J. Colbourn et Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Chapman & Hall/CRC, Boca Raton, Florida, coll. « Discrete Mathematics and its Applications (Boca Raton) », , 2e éd., p. 353–355.
  5. ↑ Marston Conder, Aleksander Malnič, Dragan Marušič, Tomaž Pisanski et Primož Potočnik, « The Ljubljana Graph », IMFM Preprint 40-845, University of Ljubljana Department of Mathematics,‎ (lire en ligne).

Liens externes