Gráfico universal

Un gráfico universal es un gráfico infinito que contiene cualquier gráfico finito (o como mucho contable ) como un subgráfico generado . Un gráfico universal de este tipo fue construido por primera vez por R. Rado [1] [2] y este gráfico ahora se llama gráfico de Rado o gráfico aleatorio. Trabajos más recientes [3] [4] se centran en grafos universales para la familia de grafos F . Es decir, un grafo infinito perteneciente a F que contiene todos los grafos finitos de la familia F. Por ejemplo, los gráficos de Hanson son universales en este sentido para gráficos sin i -cliques.

Un gráfico universal para una familia de gráficos F también puede entenderse como un miembro de una secuencia de gráficos finitos que contienen todos los gráficos de F . Por ejemplo, cualquier árbol finito es un subgrafo de un grafo de hipercubo lo suficientemente grande [5] para que se pueda decir que el hipercubo es un grafo universal para árboles. Sin embargo, este no es el gráfico más pequeño de este tipo: se sabe que existe un gráfico universal para árboles con n vértices, que contiene solo n vértices y O ( n  log  n ) aristas, y este gráfico es óptimo [6] . Se puede usar una construcción basada en el teorema de la partición plana para mostrar que los gráficos planos con n vértices tienen gráficos universales con aristas O( n 3/2 ) , y que los gráficos planos de grado acotado tienen gráficos universales con aristas O( n  log  n ) [7] [8] [9] . La conjetura de Sumner establece que los torneos son universales para poliárboles en el sentido de que cualquier torneo con 2n  − 2 vértices contiene cualquier poliárbol con n vértices como subárbol [10] .

Una familia de gráficos F tiene un gráfico universal de tamaño polinomial que contiene cualquier gráfico con n vértices como un subgráfico generado si y solo si tiene un esquema de etiquetado adyacente en el que los vértices se pueden etiquetar con O (log  n ) cadenas de bits tal de tal manera que el algoritmo puede determinar si los vértices son adyacentes por las etiquetas de esos vértices. Si existe un grafo de este tipo, los vértices de cualquier grafo en F se pueden etiquetar con etiquetas de los vértices correspondientes del grafo universal, y viceversa, si existe un esquema de etiquetado, se puede construir un grafo universal que contenga todas las etiquetas posibles [ 11] .

En la terminología matemática más antigua, la frase "gráfico universal" a veces se usaba para un gráfico completo .

Notas

  1. ↑ Rado, 1964 , pág. 331–340.
  2. ↑ Rado, 1967 , pág. 83–85.
  3. ↑ Goldstern, Kojman, 1996 , pág. 319–326.
  4. ↑ Cherlin, Shelah, Shi, 1999 , pág. 454–491.
  5. ↑ Wu, 1985 , pág. 238–249.
  6. ↑ Chung, Graham, 1983 , pág. 203–211.
  7. ↑ Babai, Chung, Erdős, Graham, Spencer, 1982 , p. 21–26.
  8. ↑ Bhatt, Chung, Leighton, Rosenberg 1989 , p. 145.
  9. ↑ Chung, 1990 , pág. 17–34.
  10. ↑ Conjetura del Torneo Universal de Sumner Archivado el 27 de febrero de 2014 en Wayback Machine , Douglas B. West, consultado el 17 de septiembre de 2010.
  11. ↑ Kannan, Naor, Rudich, 1992 , pág. 596–603.

Literatura

Enlaces