Voir la source de Graphe de Kneser

{{Confusion|Graphe biparti de Kneser}}
{{Infobox Graphe
| nom = Graphe de Kneser
| image = Kneser-5-2.svg
| légende = Le graphe de Kneser ''KG''<sub>5,2</sub>, isomorphe au [[graphe de Petersen]]
| notation = ''KG''<sub>n,k</sub>
| sommets = <math>C_n^k</math>
| arêtes = 
| distribution = régulier de degré <math>C_{n-k}^k</math>
| diamètre = <math>\left\lceil \frac{k-1}{n-2k} \right\rceil + 1</math>
| nombre chromatique = ''n''-2''k''+2
| maille = 
| propriétés = 
}} 

En [[théorie des graphes]], les '''graphes de Kneser''' forment une famille infinie de graphes. Le graphe de Kneser ''KG''<sub>n,k</sub> est un [[graphe (mathématiques discrètes)|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 <math>C_n^k</math>, le nombre de [[Combinaison (mathématiques)|combinaison]] de ''k'' parmi ''n'', et il est [[graphe régulier|régulier]] de degré <math>C_{n-k}^k</math>.

== Histoire ==
En 1955, le mathématicien [[Martin Kneser]] se pose la question suivante :
{{Citation|Si on considère la famille des ''k''-sous-ensembles d'un ensemble de cardinal ''n'', on peut partitionner cette famille en ''n''-2''k''+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''-2''k''+1 classes avec la même propriété ?}}
Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice<ref>{{article|lang=en|nom=Kneser|prénom=M.|titre=Aufgabe 360|url=http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN37721857X_0058&DMDID=DMDLOG_0020|revue=Jahresber. [[Deutsche Mathematiker-Vereinigung|DMV]]|volume=58|année=1956}}</ref>.

En 1978 [[László Lovász]] étudie la conjecture de Kneser comme un problème de théorie des graphes<ref>{{article|lang=en|nom=Lovász|prénom=L.|titre=Kneser's Conjecture, Chromatic Numbers and Homotopy|revue=J. Comb. Th. A|volume=25|p.=319-324|année=1978}}</ref>. Il introduit les graphes de Kneser puis démontre que le nombre chromatique du graphe ''KG''<sub>n,k</sub> est égal à ''n''-2''k''+2, ce qui prouve la conjecture de Kneser<ref>[[Imre Bárány]] 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]]''.</ref>. L'approche topologique pour résoudre un problème combinatoire est très novatrice et engendre un nouveau domaine : la combinatoire topologique<ref>{{article|lang=en|prénom=Mark de|nom=Longueville|titre=25 years proof of the Kneser conjecture: The advent of topological combinatorics|revue=[[European Mathematical Society|EMS]] Newsletter|lieu=Southampton, Hampshire|p.=16-19|url=http://emis.kaist.ac.kr/newsletter/current/current9.pdf|année=2004}}</ref>.

== Propriétés ==
Le [[diamètre (théorie des graphes)|diamètre]] d'un graphe de Kneser [[graphe connexe|connexe]] ''KG''<sub>n, k</sub>, l'excentricité maximale de ses sommets, est égal à<ref>{{article|langue=en
  | titre = On the diameter of Kneser graphs
  | auteur = Valencia-Pabon, Mario; Vera, Juan-Carlos
  | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
  | volume = 305
  | numéro = 1–3
  | pages = 383–385
  | année = 2005
  | doi = 10.1016/j.disc.2005.10.001}}</ref> :
:<math>\left\lceil \frac{k-1}{n-2k} \right\rceil + 1</math>

Quand <math>n \ge 3k</math>, le graphe de Kneser  ''KG''<sub>n, k</sub> est [[graphe hamiltonien|hamiltonien]]<ref>{{article|langue=en
  | auteur = Chen, Ya-Chen
  | journal = Journal of Combinatorial Theory, Series B
  | titre = Kneser graphs are Hamiltonian for ''n'' ≥ 3''k''
  | volume = 80
  | année = 2000
  | pages = 69–79
  | url = http://math.la.asu.edu/~cchen/kneser.ps
  | doi = 10.1006/jctb.2000.1969}}</ref>. Il est actuellement conjecturé que tous les graphes de Kneser connexes sont hamiltoniens sauf ''KG''<sub>5,2</sub>, le [[graphe de Petersen]]. Une recherche exhaustive sur ordinateur a révélé que cette conjecture était vraie pour <math>n \le 27</math><ref>{{Ouvrage|langue= anglais |auteur= Shields, Ian Beaumont |titre= Hamilton Cycle Heuristics in Hard Graphs |éditeur= Ph.D. thesis, North Carolina State University |année= 2004 |isbn=|lire en ligne= http://repository.lib.ncsu.edu/ir/handle/1840.16/3808 }}</ref>{{,}}<ref>Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." Bull. Inst. Combin. Appl. 40, 13-22, 2004</ref>.

Quand <math>n < 3k</math>, 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 <math>n \ge 2k+2</math>, pour des valeurs de <math>n</math> proche de <math>2k</math>, la longueur du cycle impair le plus court dans le graphe de Kneser est variable<ref>{{article|langue=en
  | titre = The odd girth of the generalised Kneser graph
  | auteur = Denley, Tristan
  | journal = European Journal of Combinatorics
  | volume = 18
  | numéro = 6
  | année = 1997
  | pages = 607–611
  | doi = 10.1006/eujc.1996.0122}}</ref>.

== Cas particuliers ==
*Le [[graphe de Petersen]] est isomorphe au graphe ''KG''<sub>5,2</sub>.
*Le [[graphe complet]] ''K''<sub>''n''</sub> est isomorphe au graphe ''KG''<sub>n,1</sub>.
*En 1980, Hall prouve qu'il existe exactement 3 graphes étant [[graphe local|localement le graphe de Petersen]]<ref>Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.</ref>. Il s'agit du [[graphe de Conway-Smith]], du [[graphe de Hall]] et du graphe de Kneser ''KG''<sub>7,2</sub>.

== Notes et références ==
{{reflist}}

== Liens externes ==
* {{MathWorld|nom_url=KneserGraph|titre=Kneser Graph}}
* {{Planetmath|titre=Kneser Graphs}}

{{Portail|mathématiques|informatique théorique}}

{{DEFAULTSORT:Kneser, graphe de}}
[[Catégorie:Famille de graphes|Petersen]]