Graphe de Kneser

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Graphe biparti de Kneser.
Graphe de Kneser
Image illustrative de l'article Graphe de Kneser
Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen

Notation KGn,k
Nombre de sommets C_n^k
Distribution des degrés régulier de degré C_{n-k}^k
Diamètre \left\lceil \frac{k-1}{n-2k} \right\rceil + 1
Nombre chromatique n-2k+2

En théorie des graphes, les graphes de Kneser forment une famille infinie de graphes. Le graphe de Kneser KGn,k est un graphe simple dont les sommets correspondent aux sous-ensembles à k éléments d'un ensemble à n éléments. Deux sommets sont reliés s'ils correspondent à des sous-ensembles disjoints. Son ordre est donc égal C_n^k, le nombre de combinaison de k parmi n, et il est régulier de degré C_{n-k}^k.

Histoire[modifier | modifier le code]

En 1955, le mathématicien Martin Kneser se pose la question suivante : « Si on considère la famille des k-sous-ensembles d'un ensemble de cardinal n, on peut partitionner cette famille en n-2k+2 classes de telle façon qu'aucune paire de k-sous-ensembles dans une classe donnée ne soit disjointe. Est-il possible de partitionner la famille considérée en n-2k+1 classes avec la même propriété ? » Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice[1].

En 1978 László Lovász étudie la conjecture de Kneser comme un problème de théorie des graphes[2]. Il introduit les graphes de Kneser puis démontre que le nombre chromatique du graphe KGn,k est égal à n-2k+2, ce qui prouve la conjecture de Kneser[3]. L'approche topologique pour résoudre un problème combinatoire est très novatrice en engendre un nouveau domaine : la combinatoire topologique[4].

Propriétés[modifier | modifier le code]

Le diamètre d'un graphe de Kneser connexe KGn, k, l'excentricité maximale de ses sommets, est égal à[5] :

\left\lceil \frac{k-1}{n-2k} \right\rceil + 1

Quand n \ge 3k, le graphe de Kneser KGn, k est hamiltonien[6]. Il est actuellement conjecturé que tous les graphes de Kneser connexes sont hamiltoniens sauf KG5,2, le graphe de Petersen. Une recherche exhaustive sur ordinateur a révélé que cette conjecture était vraie pour n \le 27[7],[8].

Quand n < 3k, le graphe de Kneser est un graphe sans triangle. Plus généralement, bien que le graphe de Kneser contienne toujours un cycle de longueur 4 quand n \ge 2k+2, pour des valeurs de n proche de 2k, la longueur du cycle impair le plus court dans le graphe de Kneser est variable[9].

Cas particuliers[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (en) M. Kneser, « Aufgabe 360 », Jahresber. DMV, vol. 58,‎ (lire en ligne)
  2. (en) L. Lovász, « Kneser's Conjecture, Chromatic Numbers and Homotopy », J. Comb. Th. A, vol. 25,‎ , p. 319-324
  3. Imre Bárány (en) et Joshua Greene (lauréat 2003 du prix Morgan) ont simplifié la preuve en 2002 : cf. Martin Aigner et Günter M. Ziegler, Raisonnements divins.
  4. (en) Mark de Longueville, « 25 years proof of the Kneser conjecture: The advent of topological combinatorics », EMS Newsletter, Southampton, Hampshire,‎ , p. 16-19 (lire en ligne)
  5. (en) Valencia-Pabon, Mario; Vera, Juan-Carlos, « On the diameter of Kneser graphs », Discrete Mathematics, vol. 305, no 1–3,‎ , p. 383–385 (DOI 10.1016/j.disc.2005.10.001)
  6. (en) Chen, Ya-Chen, « Kneser graphs are Hamiltonian for n ≥ 3k », Journal of Combinatorial Theory, Series B, vol. 80,‎ , p. 69–79 (DOI 10.1006/jctb.2000.1969, lire en ligne)
  7. (en) Shields, Ian Beaumont, Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, North Carolina State University,‎ (lire en ligne)
  8. Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." Bull. Inst. Combin. Appl. 40, 13-22, 2004
  9. (en) Denley, Tristan, « The odd girth of the generalised Kneser graph », European Journal of Combinatorics, vol. 18, no 6,‎ , p. 607–611 (DOI 10.1006/eujc.1996.0122)
  10. Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.

Liens externes[modifier | modifier le code]