En matemáticas , un gráfico universal es un gráfico infinito que contiene cada gráfico finito (o como mucho contable ) como un subgrafo inducido . Un gráfico universal de este tipo fue construido por primera vez por Richard Rado [1] [2] y ahora se denomina gráfico de Rado o gráfico aleatorio. Un trabajo más reciente [3] [4] se ha centrado en los gráficos universales para una familia gráfico F : es decir, un gráfico de infinito que pertenece a F que contiene todos los gráficos finitos en F . Por ejemplo, las gráficas de Hensonson universales en este sentido para los i gráficos sin -clique.
Una gráfica universal para una familia F de gráficas también puede referirse a un miembro de una secuencia de gráficas finitas que contiene todas las gráficas en F ; por ejemplo, cada árbol finito es un subgrafo de un hipercubo grafo suficientemente grande [5] por lo que se puede decir que un hipercubo es un grafo universal para árboles. Sin embargo, no es el gráfico más pequeño de este tipo: se sabe que hay un gráfico universal para n árboles de vértices, con solo n vértices y O ( n log n ) aristas, y que esto es óptimo. [6] Se puede usar una construcción basada en el teorema del separador plano para mostrar que los gráficos planos de n - vértices tienen gráficos universales con bordes O ( n 3/2 ) , y que los gráficos planos de grados acotados tienen gráficos universales con O ( n log n ) bordes. [7] [8] [9] También es posible construir gráficas universales para gráficas planas que tienen n 1+ o (1) vértices. [10] La conjetura de Sumner establece que los torneos son universales para polytrees , en el sentido de que cada torneo con 2 n - 2 vértices contiene cada polytree con n vértices como subgrafo. [11]
Una familia F de grafos tiene un grafo universal de tamaño polinomial, que contiene cada grafo de n -vértices como un subgrafo inducido , si y solo si tiene un esquema de etiquetado de adyacencia en el que los vértices pueden etiquetarse con cadenas de bits de O (log n ) bits tales que un algoritmo puede determinar si dos vértices son adyacentes al examinar sus etiquetas. Porque, si existe un grafo universal de este tipo, los vértices de cualquier grafo en F pueden ser etiquetados por las identidades de los vértices correspondientes en el grafo universal y, a la inversa, si existe un esquema de etiquetado, entonces se puede construir un grafo universal que tenga un vértice. para cada etiqueta posible. [12]
En terminología matemática más antigua, la frase "gráfico universal" a veces se usaba para denotar un gráfico completo .
La noción de gráfico universal se ha adaptado y utilizado para resolver juegos de pago medio. [13]
Referencias
- ^ Rado, R. (1964). "Gráficos universales y funciones universales" . Acta Arithmetica . 9 (4): 331–340. doi : 10.4064 / aa-9-4-331-340 . Señor 0172268 .
- ^ Rado, R. (1967). "Gráficos universales". Un seminario de teoría de grafos . Holt, Rinehart y Winston. págs. 83–85. Señor 0214507 .
- ^ Goldstern, Martin; Kojman, Menachem (1996). "Gráficos sin flechas universales". Acta Mathematica Hungarica . 1973 (4): 319–326. arXiv : math.LO / 9409206 . doi : 10.1007 / BF00052907 . Señor 1428038 .
- ^ Cherlin, Greg; Sela, Saharon; Shi, Niandong (1999). "Gráficos universales con subgrafos prohibidos y cierre algebraico". Avances en Matemática Aplicada . 22 (4): 454–491. arXiv : math.LO / 9809202 . doi : 10.1006 / aama.1998.0641 . Señor 1683298 .
- ^ Wu, AY (1985). "Incrustación de redes de árboles en hipercubos". Revista de Computación Paralela y Distribuida . 2 (3): 238–249. doi : 10.1016 / 0743-7315 (85) 90026-7 .
- ^ Chung, FRK ; Graham, RL (1983). "Sobre gráficos universales para árboles de expansión" (PDF) . Revista de la Sociedad Matemática de Londres . 27 (2): 203–211. CiteSeerX 10.1.1.108.3415 . doi : 10.1112 / jlms / s2-27.2.203 . Señor 0692525 ..
- ^ Babai, L .; Chung, FRK ; Erdős, P .; Graham, RL ; Spencer, JH (1982). "En gráficos que contienen todos los gráficos dispersos". En Rosa, Alejandro; Sabidussi, Gert; Turgeon, Jean (eds.). Teoría y práctica de la combinatoria: colección de artículos en honor a Anton Kotzig con motivo de su sexagésimo cumpleaños (PDF) . Annals of Discrete Mathematics. 12 . págs. 21-26. Señor 0806964 .
- ^ Bhatt, Sandeep N .; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989). "Gráficos universales para árboles de grados acotados y gráficos planos". Revista SIAM de Matemática Discreta . 2 (2): 145-155. doi : 10.1137 / 0402014 . Señor 0990447 .
- ^ Chung, Fan RK (1990). "Teoremas del separador y sus aplicaciones". En Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (eds.). Rutas, flujos y diseño VLSI . Algoritmos y Combinatoria. 9 . Springer-Verlag. págs. 17–34 . ISBN 978-0-387-52685-0. Señor 1083375 .
- ^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), Esquemas de etiquetado de adyacencia para gráficos planos (y más allá) , arXiv : 2003.04280
- ^ Conjetura del torneo universal de Sumner , Douglas B. West, consultado el 17 de septiembre de 2010.
- ^ Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992), "Representación implícita de gráficos", SIAM Journal on Discrete Mathematics , 5 (4): 596–603, doi : 10.1137 / 0405049 , MR 1186827.
- ^ Czerwiński, Wojciech; Daviaud, Laure; Fijalkow, Nathanaël; Jurdziński, Marcin; Lazić, Ranko; Parys, Paweł (27 de julio de 2018). "Los árboles universales crecen dentro de los autómatas de separación: límites inferiores cuasi-polinomiales para juegos de paridad". arXiv : 1807.10546 [ cs.FL ].
enlaces externos
- La fórmula panarborial , "Teorema del día" sobre gráficas universales para árboles