Teorema de Graham-Pollak

Partición de las aristas del grafo completo en cinco subgrafos bipartitos completos: (rojo claro), (azul claro), (amarillo) y dos copias de (rojo oscuro y azul oscuro). Según el teorema de Graham-Pollak, no es posible una partición en menos de cinco subgrafos bipartitos completos. ${\displaystyle K_{6}}$ ${\displaystyle K_{2,2}}$ ${\displaystyle K_{2,3}}$ ${\displaystyle K_{1,3}}$ ${\displaystyle K_{1,1}}$

En teoría de grafos , el teorema de Graham-Pollak establece que las aristas de un grafo completo de vértice no se pueden dividir en menos de grafos bipartitos completos . ^[1] Fue publicado por primera vez por Ronald Graham y Henry O. Pollak en dos artículos en 1971 y 1972 (acreditando a Hans Witsenhausen por un lema clave), en relación con una aplicación a circuitos de conmutación telefónica. ^{[2] [3]} ${\displaystyle n}$ ${\displaystyle n-1}$

Desde entonces, el teorema se ha vuelto muy conocido y se ha estudiado y generalizado repetidamente en la teoría de grafos, en parte debido a su elegante prueba utilizando técnicas de la teoría de grafos algebraicos . ^{[4] [5] [6] [7] [8]} Más firmemente, Aigner y Ziegler (2018) escriben que todas las pruebas se basan de alguna manera en el álgebra lineal : "no se conoce ninguna prueba combinatoria para este resultado". ^[1]

Construcción de una partición óptima

Es fácil obtener una partición en gráficos bipartitos exactamente completos: simplemente ordene los vértices y, para cada vértice excepto el último, forme una estrella que lo conecte con todos los vértices posteriores en el ordenamiento. ^[1] También son posibles otras particiones. ${\displaystyle n-1}$

Prueba de optimalidad

La prueba del teorema de Graham-Pollak descrita por Aigner y Ziegler (2018) (siguiendo a Tverberg 1982) define una variable real para cada vértice , donde denota el conjunto de todos los vértices del grafo. Sean los lados izquierdo y derecho del grafo bipartito n y , respectivamente, y para cualquier conjunto de vértices definidos como la suma de las variables para los vértices en : ${\displaystyle x_{i}}$ ${\displaystyle v_{i}\in V}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle L_{k}}$ ${\displaystyle R_{k}}$ ${\displaystyle S}$ ${\displaystyle X(S)}$ ${\displaystyle S}$

${\displaystyle X(S)=\sum _{v_{i}\in S}x_{i}.}$

Entonces, en términos de esta notación, el hecho de que los grafos bipartitos particionen los bordes del grafo completo se puede expresar como la ecuación

${\displaystyle \sum _{i<j}x_{i}x_{j}=\sum _{k}X(L_{k})X(R_{k}).}$

Consideremos ahora el sistema de ecuaciones lineales que establece y para cada . Cualquier solución de este sistema de ecuaciones también obedecería a las ecuaciones no lineales ${\displaystyle X(V)=0}$ ${\displaystyle X(L_{k})=0}$ ${\displaystyle k}$

${\displaystyle {\begin{aligned}0&=X(V)^{2}={\Bigl (}\sum _{i}x_{i}{\Bigr )}^{2}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{i<j}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}}}$

Pero una suma de cuadrados de variables reales sólo puede ser cero si todas las variables individuales son cero, la solución trivial del sistema de ecuaciones lineales. Si hubiera menos de grafos bipartitos completos, el sistema de ecuaciones tendría menos de ecuaciones con incógnitas y tendría una solución no trivial, una contradicción. Por lo tanto, el número de grafos bipartitos completos debe ser al menos . ^{[1] [4]} ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Problemas relacionados

Etiquetado de distancia

Graham y Pollak estudian un problema de etiquetado de grafos más general , en el que los vértices de un grafo deberían etiquetarse con cadenas de igual longitud de los caracteres "0", "1" y "✶", de tal manera que la distancia entre dos vértices sea igual al número de posiciones de cadena donde un vértice está etiquetado con un 0 y el otro con un 1. Un etiquetado como este sin caracteres "✶" daría una incrustación isométrica en un hipercubo , algo que solo es posible para grafos que son cubos parciales , y en uno de sus artículos Graham y Pollak llaman a un etiquetado que permite caracteres "✶" una incrustación en un "cubo aplastado". ^[3]

Para cada posición de las cadenas de etiquetas, se puede definir un grafo bipartito completo en el que un lado de la bipartición consiste en los vértices etiquetados con 0 en esa posición y el otro lado consiste en los vértices etiquetados con 1, omitiendo los vértices etiquetados "✶". Para el grafo completo, cada dos vértices están a una distancia de uno de cada uno, por lo que cada arista debe pertenecer exactamente a uno de estos grafos bipartitos completos. De esta manera, un etiquetado de este tipo para el grafo completo corresponde a una partición de sus aristas en grafos bipartitos completos, con las longitudes de las etiquetas correspondientes al número de grafos en la partición. ^[3]

Conjetura de Alon-Saks-Seymour

Noga Alon , Michael Saks y Paul Seymour formularon una conjetura a principios de los años 1990 que, de ser cierta, generalizaría significativamente el teorema de Graham-Pollak: conjeturaron que, siempre que un grafo de número cromático tiene sus aristas divididas en subgrafos bipartitos completos, se necesitan al menos subgrafos. De manera equivalente, su conjetura establece que las uniones disjuntas de aristas de grafos bipartitos completos siempre se pueden colorear con, como máximo, colores. La conjetura fue refutada por Huang y Sudakov en 2012, quienes construyeron familias de grafos formados como uniones disjuntas de aristas de grafos bipartitos completos que requieren colores. ^[9] Más firmemente, el número de colores puede ser tan grande como , ajustado hasta el término en el exponente. ^[10] ${\displaystyle k+1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle k}$ ${\displaystyle \Omega (k^{6/5})}$ ${\displaystyle \exp \log ^{2-o(1)}k}$ ${\displaystyle o(1)}$

Partición biclique

El problema de partición biclique toma como entrada un grafo arbitrario no dirigido y pide una partición de sus aristas en un número mínimo de grafos bipartitos completos. Es NP-hard , pero manejable con parámetros fijos . El mejor algoritmo de aproximación conocido para el problema tiene una relación de aproximación de . ^{[11] [12]} ${\displaystyle O(n/\log n)}$

Referencias

1. Aigner, Martin ; Ziegler, Günter M. (2018), Pruebas del LIBRO (6.ª ed.), Springer, págs. 79-80, doi :10.1007/978-3-662-57265-8, ISBN 978-3-662-57265-8
2. Graham, RL ; Pollak, HO (1971), "Sobre el problema de direccionamiento para conmutación de bucle", The Bell System Technical Journal , 50 (8): 2495–2519, doi :10.1002/j.1538-7305.1971.tb02618.x, MR  0289210
3. Graham, RL ; Pollak, HO (1972), "Sobre la incrustación de gráficos en cubos aplastados", Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicado a la memoria de JWT Youngs) , Lecture Notes in Mathematics, vol. 303, págs. 99-110, MR  0332576
4. Tverberg, H. (1982), "Sobre la descomposición de en grafos bipartitos completos", Journal of Graph Theory , 6 (4): 493–494, doi :10.1002/jgt.3190060414, MR  0679606 ${\displaystyle K_{n}}$
5. Peck, GW (1984), "Una nueva prueba de un teorema de Graham y Pollak", Matemáticas discretas , 49 (3): 327–328, doi :10.1016/0012-365X(84)90174-2, MR  0743808
6. Cioabă, Sebastian M.; Tait, Michael (2013), "Variaciones sobre un tema de Graham y Pollak", Discrete Mathematics , 313 (5): 665–676, CiteSeerX 10.1.1.717.6351 , doi :10.1016/j.disc.2012.12.001, MR  3009433 
7. Vishwanathan, Sundar (2013), "Una prueba de conteo del teorema de Graham-Pollak", Matemáticas discretas , 313 (6): 765–766, arXiv : 1007.1553 , doi : 10.1016/j.disc.2012.12.017 , MR  3010739
8. Líder, Imre ; Tan, Ta Sheng (2018), "Límites mejorados para el problema de Graham-Pollak para hipergrafos", Electronic Journal of Combinatorics , 25 (1): Artículo n.º 1.4, arXiv : 1708.01898 , doi :10.37236/7206, MR  3761918
9. Huang, Hao; Sudakov, Benny (2012), "Un contraejemplo de la conjetura de Alon–Saks–Seymour y problemas relacionados", Combinatorica , 32 (2): 205–219, arXiv : 1002.4687 , doi :10.1007/s00493-012-2746-4, MR  2927639
10. Balodis, Kaspars; Ben-David, Shalev; Göös, Mika; Jain, Siddhartha; Kothari, Robin (2021), "DNF inequívocos y Alon–Saks–Seymour", 62.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2021, Denver, CO, EE. UU., 7-10 de febrero de 2022 , págs. 116–124, arXiv : 2102.08348 , doi :10.1109/FOCS52979.2021.00020, ISBN 978-1-6654-2055-6
11. Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniël; Szeider, Stefan (2009), "Cobertura de gráficos con pocos subgráficos bipartitos completos", Theoretical Computer Science , 410 (21–23): 2045–2053, doi :10.1016/j.tcs.2008.12.059, MR  2519293
12. Chandran, Sunil; Issac, Davis; Karrenbauer, Andreas (2017), "Sobre la complejidad parametrizada de la cobertura y partición biclique", en Guo, Jiong; Hermelin, Danny (eds.), 11.º Simposio internacional sobre computación parametrizada y exacta (IPEC 2016) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 63, Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, págs. 11:1–11:13, doi : 10.4230/LIPIcs.IPEC.2016.11 , ISBN 978-3-95977-023-1