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 ${\displaystyle C_{n}^{k}}$, le nombre de combinaison de k parmi n, et il est régulier de degré ${\displaystyle C_{n-k}^{k}}$.

Graphe de Kneser
Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen
Notation	KGn,k
Nombre de sommets	${\displaystyle C_{n}^{k}}$
Distribution des degrés	régulier de degré ${\displaystyle C_{n-k}^{k}}$
Diamètre	${\displaystyle \left\lceil {\frac {k-1}{n-2k}}\right\rceil +1}$
Nombre chromatique	n-2k+2
modifier

Histoire

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].

Propriétés

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].

Cas particuliers

• 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^[10]. Il s'agit du graphe de Conway-Smith, du graphe de Hall et du graphe de Kneser KG_7,2.