Graphe de Kneser

En théorie des graphes, les graphes de Kneser forment une famille infinie de graphes. Le graphe de Kneser KG_n,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$.

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.

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 KG_n,k est égal à n-2k+2, ce qui prouve la conjecture de Kneser. L'approche topologique pour résoudre un problème combinatoire est très novatrice en engendre un nouveau domaine : la combinatoire topologique.

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

Quand $n\ge 3k$, le graphe de Kneser graph KG_n,k est hamiltonien. Il est actuellement conjecturé que tous les graphes de Kneser connexes sont Hamiltoniens sauf KG_5,2, le graphe de Petersen. Une recherche exhaustive sur ordinateur a révélé que cette conjecture était vraie pour $n\le 27$.

• Le graphe de Petersen est isomorphe au graphe KG_5,2.
• Le graphe complet K_n est isomorphe au graphe KG_n,1.
• En 1980, Hall prouve qu'il existe exactement 3 graphes étant localement le graphe de Petersen. Il s'agit du graphe de Conway-Smith du graphe de Hall et du graphe de Kneser KG_7,2.