Théorème de Graham-Pollak

En théorie des graphes, le théorème de Graham-Pollak affirme que les arêtes d'un graphe complet à  sommets ne peut être partitionné en moins de  graphes bipartis complets. 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éphonique.  

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 graphes. Plus précisément, Aigner & Ziegler é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 ».

Construction d'une partition optimale 
Une partition en exactement  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'ordre. D'autres partitions sont également possibles.

Preuve de l'optimalité 
La preuve du théorème de Graham-Pollak décrite par Aigner & Ziegler (qui suivent ) définit une variable réelle  pour chaque sommet , où  désigne l'ensemble des sommets du graphe. Notons   et  les sommets des côtés gauche et droit du -ième graphe biparti, et  notons , pour tout ensemble  des sommets,  la somme des variables pour les sommets  : 

 .

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

 .

Considérons maintenant le système d'équations linéaires qui donne  et  pour chaque . Toute solution à ce système d'équations vérifie également les équations non linéaires :

 .

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  graphes bipartis complets, le système d'équations aurait moins de  équations en  inconnues et il aurait une solution non triviale, une contradiction. Le nombre de graphes bipartis complets doit donc être au moins .

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é ». 

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

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  en sous-graphes bipartis complets, doit comporter au moins  sous-graphes. De manière équivalente, leur conjecture dit que des unions de  graphes bipartis complets sans arêtes communes peuvent toujours être colorés en  au plus  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  graphes bipartis complets et qui requièrent  couleurs.

Partition biclique 

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 .

Références

Articles connexes 
 Dimension bipartie
 Couverture par sous-graphes bipartis complets

Théorie algébrique des graphes
Graham-Pollak