Théorème de Graham-Pollak

Partition des arêtes du graphe complet $K_6$ en cinq sous-graphes bipartis complets : $K_{2,2}$ (rouge clair), $K_{2,3}$ (bleu clair), $K_{1,3}$ (jaune) et deux exemplaires de $K_{1,1}$ (rouge foncé et bleu foncé). Selon le théorème de Graham-Pollak, une partition en moins de cinq sous-graphes bipartis complets n'est pas possible.

En théorie des graphes, le théorème de Graham-Pollak affirme que les arêtes d'un graphe complet à $n$ sommets ne peut être partitionné en moins de $n-1$ graphes bipartis completsModèle:Références multiples. Il a d'abord été publié par Ronald Graham et Henry O. Pollak dans deux articles en 1971 et 1972, dans le cadre d'une application aux circuits de commutation téléphoniqueModèle:Références multiples.

Le théorème est depuis devenu bien connu et a été étudié et généralisé à plusieurs reprises en théorie des graphes, en partie à cause de sa preuve élégante utilisant des techniques de la théorie algébrique des graphesModèle:Références multiples. Plus précisément, Aigner & ZieglerModèle:Références multiples écrivent que toutes les preuves sont basées d'une manière ou d'une autre sur l'algèbre linéaire : « aucune preuve combinatoire pour ce résultat n'est connue »Modèle:Références multiples.

Construction d'une partition optimale

Une partition en exactement $n-1$ graphes bipartis complets est facile à obtenir : il suffit d'ordonner les sommets et, pour chaque sommet à l'exception du dernier, de former un graphe étoile le reliant à tous les sommets supérieurs dans l'ordreModèle:Références multiples. D'autres partitions sont également possibles.

Preuve de l'optimalité

La preuve du théorème de Graham-Pollak décrite par Aigner & ZieglerModèle:Références multiples (qui suivent Modèle:Référence Harvard sans parenthèses) définit une variable réelle $x_i$ pour chaque sommet $v_i\in V$, où $V$ désigne l'ensemble des sommets du graphe. Notons $L_k$ et $R_k$ les sommets des côtés gauche et droit du $k$-ième graphe biparti, et notons $X(S)$, pour tout ensemble $S$ des sommets, la somme des variables pour les sommets $S$ :

$X(S)=\sum _{v_i\in S}{x}_i$.

Avec ces notations, le fait que les graphes bipartis partitionnent les arêtes du graphe complet peut être exprimé par l'équation :

$\sum _{i<j}{x}_i{x}_j=\sum _{k}X(L_k)X(R_k)$.

Considérons maintenant le système d'équations linéaires qui donne $X(S)=0$ et $X(L_k)=0$ pour chaque $k$. Toute solution à ce système d'équations vérifie également les équations non linéaires :

$\begin{array}{cc}0& =X(S{)}^2=(\sum _i{x}_i{)}^2\\ & =\left(\sum _i{x}_i^2\right)+\left(2\sum _{i<k}{x}_i{x}_j\right)\\ & =\left(\sum _i{x}_i^2\right)+(2\sum _{k}X(L_k)X(R_k))\\ & =\sum _i{x}_i^2.\\ \end{array}$.

Maintenant, une somme de carrés de variables réelles ne peut être nulle que si les variables sont toutes nulles : la solution triviale au système d'équations linéaires. S'il y avait moins de $n-1$ graphes bipartis complets, le système d'équations aurait moins de $n$ équations en $n$ inconnues et il aurait une solution non triviale, une contradiction. Le nombre de graphes bipartis complets doit donc être au moins $n-1$Modèle:Références multiples.

Problèmes liés

Étiquetage en distances

Graham et Pollak étudient un problème d'étiquetage de graphes plus général, dans lequel les sommets d'un graphe sont étiquetés avec des chaînes de même longueur composées caractères "0", "1" et "✶", de telle sorte que la distance entre deux sommets quelconques est le nombre des positions des chaînes où un sommet est étiqueté avec un 0 et l'autre est étiqueté avec un 1. Un tel étiquetage, sans le caractère "✶", donne un plongement isométrique dans un hypercube, ce qui n'est possible que pour les graphes qui sont des cubes partiels, et dans l'un de leurs articles, Graham et Pollak appellent un étiquetage qui autorise des caractères "✶" un plongement dans un « cube écrasé »Modèle:Références multiples.

Pour chaque position des chaînes étiquettes, on peut définir un graphe biparti complet dans lequel un côté de la bipartition se compose des sommets étiquetés avec 0 dans cette position et l'autre côté se compose des sommets étiquetés avec 1, en omettant les sommets étiquetés "✶". Pour le graphe complet, deux sommets sont à distance un l'un de l'autre, donc chaque arête doit appartenir à exactement l'un de ces graphes complets. Ainsi, un tel étiquetage pour le graphe complet correspond à une partition de ses arêtes en graphes bipartis complets, avec les longueurs des étiquettes correspondant au nombre de graphes dans la partitionModèle:Références multiples.

Conjecture d'Alon–Saks–Seymour

Noga Alon, Michael Saks et Paul Seymour ont formulé une conjecture au début des années 1990 qui, si elle est vérifiée, fournirait une généralisation substantielle du théorème de Graham–Pollak : ils ont conjecturé que toute partition des arêtes d'un graphe de nombre chromatique $k+1$ en sous-graphes bipartis complets, doit comporter au moins $k$ sous-graphes. De manière équivalente, leur conjecture dit que des unions de $k$ graphes bipartis complets sans arêtes communes peuvent toujours être colorés en au plus $k+1$ couleurs. La conjecture a été invalidée par Huang et Sudakov en 2012, qui ont construit des familles de graphes qui sont des unions disjointes de $k$ graphes bipartis complets et qui requièrent $\mathrm{\Omega }(k^{6/5})$ couleurs.

Partition biclique

Modèle:Article détaillé Le problème de la partition biclique prend en entrée un graphe non orienté quelconque, et demande de fournir une partition de ses arêtes en un nombre minimal de graphes bipartis complets. Ce problème est NP-difficile, mais fixed-parameter tractable. le meilleur algorithme d'approximation connu pour ce problème a un facteur d'approximation en $O(n/\log n)$Modèle:Refm.

Articles connexes

• Dimension bipartie
• Couverture par sous-graphes bipartis complets