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 à $n$ sommets ne peut être partitionné en moins de $n-1$ graphes bipartis complets^[1]. 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^[2]^,^[3].

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^[4]^,^[5]^,^[6]^,^[7]^,^[8]. Plus précisément, Aigner & Ziegler^[1] é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 »^[1].

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'ordre^[1]. D'autres partitions sont également possibles.

Preuve de l'optimalité

La preuve du théorème de Graham-Pollak décrite par Aigner & Ziegler^[1]^,^[9] (qui suivent Tverberg 1982) 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{aligned}0&=X(S)^{2}={\Bigl (}\sum _{i}x_{i}{\Bigr )}^{2}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{i<k}x_{i}x_{j}{\Bigr )}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{k}X(L_{k})X(R_{k}){\Bigr )}\\&=\sum _{i}x_{i}^{2}.\\\end{aligned}}

.

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$ ^[1]^,^[4].

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é »^[3].

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^[3].

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 $\Omega (k^{6/5})$ couleurs^[10].

Partition biclique

Article détaillé : Dimension bipartie.

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)$ ^[11]^,^[12].

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graham–Pollak theorem » (voir la liste des auteurs).

1 2 3 4 5 6 Martin Aigner et Günter M. Ziegler, Proofs from THE BOOK, Springer, 2018, 6^e éd. (ISBN 978-3-662-57265-8, DOI 10.1007/978-3-662-57265-8), p. 79–80
↑ Ronald L. Graham et Henry O. Pollak, « On the addressing problem for loop switching », The Bell System Technical Journal, vol. 50,‎ 1971, p. 2495–2519 (DOI 10.1002/j.1538-7305.1971.tb02618.x, MR 289210)
1 2 3 Ronald L. Graham et Henry O. Pollak, « On embedding graphs in squashed cubes », Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs),‎ 1972, p. 99–110 (MR 0332576)
1 2 Helge Tverberg, « On the decomposition of $K_{n}$ into complete bipartite graphs », Journal of Graph Theory, vol. 6, n^o 4,‎ 1982, p. 493–494 (DOI 10.1002/jgt.3190060414, MR 679606)
↑ G. W. Peck, « A new proof of a theorem of Graham and Pollak », Discrete Mathematics, vol. 49, n^o 3,‎ 1984, p. 327–328 (DOI 10.1016/0012-365X(84)90174-2, MR 743808)
↑ Sebastian M. Cioabă et Michael Tait, « Variations on a theme of Graham and Pollak », Discrete Mathematics, vol. 313, n^o 5,‎ 2013, p. 665–676 (DOI 10.1016/j.disc.2012.12.001, MR 3009433)
↑ Sundar Vishwanathan, « A counting proof of the Graham-Pollak theorem », Discrete Mathematics, vol. 313, n^o 6,‎ 2013, p. 765–766 (DOI 10.1016/j.disc.2012.12.017, MR 3010739)
↑ Imre Leader et Ta Sheng Tan, « Improved bounds for the Graham-Pollak problem for hypergraphs », Electronic Journal of Combinatorics, vol. 25, n^o 1,‎ 2018, article n^o 1.4 (MR 3761918)
↑ Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer, 2003, 3^e éd. (ISBN 978-2-7462-4798-7), p. 73-74 « Droites du plan et decompositions de graphes »
↑ Hao Huang et Benny Sudakov, « A counterexample to the Alon-Saks-Seymour conjecture and related problems », Combinatorica, vol. 32, n^o 2,‎ 2012, p. 205–219 (DOI 10.1007/s00493-012-2746-4, MR 2927639, arXiv 1002.4687)
↑ Herbert Fleischner, Egbert Mujuni, Daniël Paulusma et Stefan Szeider, « Covering graphs with few complete bipartite subgraphs », Theoretical Computer Science, vol. 410, n^os 21-23,‎ 2009, p. 2045–2053 (DOI 10.1016/j.tcs.2008.12.059, MR 2519293)
↑ Sunil Chandran, Davis Issac et Andreas Karrenbauer, « On the parameterized complexity of biclique cover and partition », dans Jiong Guo et Danny Hermelin (éditeurs), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Dagstuhl, Germany, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 63), 2017 (ISBN 978-3-95977-023-1, DOI 10.4230/LIPIcs.IPEC.2016.11), p. 11:1–11:13