Teorema de Graham-Pollak

Partición de los bordes del gráfico 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 gráfico completo de vértice no se pueden dividir en gráficos bipartitos menos que completos . ^[1] Fue publicado por primera vez por Ronald Graham y Henry O. Pollak en dos artículos en 1971 y 1972 (dando crédito a Hans Witsenhausen por un lema clave), en relación con una aplicación a los circuitos de conmutación telefónica. ^{[2] [3]} ${\displaystyle n}$ ${\displaystyle n-1}$

Desde entonces, el teorema se ha vuelto muy conocido y estudiado y generalizado repetidamente en la teoría de grafos, en parte debido a su elegante demostración utilizando técnicas de la teoría de grafos algebraicas . ^{[4] [5] [6] [7] [8]} Más claramente, Aigner y Ziegler (2018) escriben que todas las pruebas se basan de alguna manera en á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 orden. ^[1] También son posibles otras particiones. ${\displaystyle n-1}$

Prueba de optimización

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 gráfico. Denotemos los lados izquierdo y derecho del ésimo gráfico bipartito y , respectivamente, y para cualquier conjunto de vértices, definamos como la suma de 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 gráficos bipartitos dividen los bordes del gráfico completo se puede expresar como la ecuación

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

Ahora considere el sistema de ecuaciones lineales que establece y para cada . Cualquier solución a 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 gráficas bipartitas completas, el sistema de ecuaciones tendría menos que ecuaciones con incógnitas y tendría una solución no trivial, una contradicción. Entonces 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 gráficos más general , en el que los vértices de un gráfico deben etiquetarse con cadenas de igual longitud de los caracteres "0", "1" y "✶", de tal manera que la distancia entre dos vértices cualesquiera equivalen al número de posiciones de cadena donde un vértice está etiquetado con un 0 y el otro está etiquetado 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 gráficos que son cubos parciales , y en uno de sus artículos, Graham y Pollak llaman a un etiquetado que permite que los caracteres "✶" se incrusten en un "cubo aplastado". ^[3]

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

Conjetura de Alon-Saks-Seymour

Noga Alon , Michael Saks y Paul Seymour formularon una conjetura a principios de la década de 1990 que, de ser cierta, generalizaría significativamente el teorema de Graham-Pollak: conjeturaron que, siempre que una gráfica de números cromáticos tiene sus aristas divididas en subgrafos bipartitos completos, en Se necesitan menos subgrafos. De manera equivalente, su conjetura establece que las uniones de bordes disjuntos de gráficos bipartitos completos siempre se pueden colorear con la mayoría de los colores. La conjetura fue refutada por Huang y Sudakov en 2012, quienes construyeron familias de gráficos formadas como uniones de bordes disjuntos de gráficos bipartitos completos que requieren colores. ^[9] Más claramente, el número de colores puede ser tan grande como , ajustado al término del 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 gráfico arbitrario no dirigido y solicita una partición de sus aristas en un número mínimo de gráficos bipartitos completos. Es NP-duro , 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, Martín ; Ziegler, Günter M. (2018), Pruebas del LIBRO (6.a 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 la conmutación de bucles", The Bell System Technical Journal , 50 : 2495–2519, doi :10.1002/j.1538-7305.1971.tb02618.x, MR  0289210
3. Graham, RL ; Pollak, HO (1972), "On incrustar gráficos en cubos aplastados", Teoría de grafos y aplicaciones (Proc. Conf., Western Michigan Univ., Kalamazoo, Michigan, 1972; dedicado a la memoria de JWT Youngs) , Lecture Notes en Matemáticas, vol. 303, págs. 99-110, SEÑOR  0332576
4. Tverberg, H. (1982), "Sobre la descomposición en gráficos 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ă, Sebastián M.; Tait, Michael (2013), "Variaciones sobre un tema de Graham y Pollak", Matemáticas discretas , 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 No. 1.4, 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, Señor  2927639
10. Balodis, Kaspars; Ben-David, Shalev; Göös, Mika; Jainista, Siddhartha; Kothari, Robin (2021), "Unambiguous DNFs and Alon–Saks–Seymour", 62.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2021, Denver, CO, EE. UU., 7 al 10 de febrero de 2022 , págs. arXiv : 2102.08348 , doi : 10.1109/FOCS52979.2021.00020
11. Fleischner, Herbert; Mujuni, Egbert; Paulusma, Daniel; Szeider, Stefan (2009), "Cubre gráficos con algunos subgrafos bipartitos completos", Ciencias de la Computación Teórica , 410 (21–23): 2045–2053, doi :10.1016/j.tcs.2008.12.059, MR  2519293
12. Chandran, Sunil; Isaac, Davis; Karrenbauer, Andreas (2017), "Sobre la complejidad parametrizada de la cubierta y partición biclique", en Guo, Jiong; Hermelin, Danny (eds.), XI Simposio internacional sobre computación exacta y parametrizada (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