Graphe de Kneser

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 KG_n,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 et engendre un nouveau domaine : la combinatoire topologique^[4].

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

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

Quand ${\displaystyle n\geq 3k}$, le graphe de Kneser KG_{n, k} est hamiltonien^[6]. 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 ${\displaystyle n\leq 27}$^[7],[8].

Quand ${\displaystyle 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 ${\displaystyle n\geq 2k+2}$, pour des valeurs de ${\displaystyle n}$ proche de ${\displaystyle 2k}$, la longueur du cycle impair le plus court dans le graphe de Kneser est variable^[9].