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 , le nombre de combinaisons de k parmi n, et il est régulier de degré .

Histoire En 1955, le mathématicien Martin Kneser se pose la question suivante :

Kneser conjecture que ce n'est pas possible et le publie sous forme d'un exercice.

En 1978 László Lovász étudie la conjecture de Kneser comme un problème de théorie des graphes. 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 KneserImre 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.. L'approche topologique pour résoudre un problème combinatoire est très novatrice et engendre un nouveau domaine : la combinatoire topologique.

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

Quand , le graphe de Kneser KGn, k est hamiltonien. 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 Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." Bull. Inst. Combin. Appl. 40, 13-22, 2004.

Quand , 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 , pour des valeurs de proche de , la longueur du cycle impair le plus court dans le graphe de Kneser est variable.

Cas particuliers Le graphe de Petersen est isomorphe au graphe KG5,2. Le graphe complet Kn est isomorphe au graphe KGn,1. En 1980, Hall prouve qu'il existe exactement 3 graphes étant localement le graphe de PetersenHall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.. Il s'agit du graphe de Conway-Smith, du graphe de Hall et du graphe de Kneser KG7,2.

Notes et références

Liens externes

Petersen