Gráfico universal

En matemáticas , un grafo universal es un grafo infinito que contiene a cada grafo finito (o como máximo numerable ) como subgrafo inducido. Richard Rado construyó por primera vez un grafo universal de este tipo ^{[ 1 ] [ 2 ]} , que ahora se conoce como grafo de Rado o grafo aleatorio. Trabajos más recientes ^{[ 3 ] [ 4 ]} se han centrado en grafos universales para una familia de grafos F : es decir, un grafo infinito perteneciente a F que contiene a todos los grafos finitos de F. Por ejemplo, los grafos de Henson son universales en este sentido para los grafos libres de i -cliques.

Un grafo universal para una familia F de grafos también puede referirse a un miembro de una secuencia de grafos finitos que contiene todos los grafos en F ; por ejemplo, todo árbol finito es un subgrafo de un grafo hipercubo suficientemente grande ^{[ 5 ]} , por lo que se puede decir que un hipercubo es un grafo universal para árboles. Sin embargo, no es el grafo más pequeño de este tipo: se sabe que hay un grafo universal para árboles de n vértices, con solo n  vértices y O( n  log n )  aristas, y que este es óptimo. ^{[ 6 ]} Una construcción basada en el teorema del separador planar puede usarse para mostrar que los grafos planares de n vértices tienen grafos universales con O( n³ ^/² ) aristas, y que los grafos planares de grado acotado tienen grafos universales con O( n log n ) aristas. ^{[ 7 ] [ 8 ] [ 9 ]} También es posible construir grafos universales para grafos planares que tienen n¹ ^{+ o (1)} vértices. ^{[ 10 ]} La conjetura de Sumner afirma que los torneos son universales para los poliárboles , en el sentido de que todo torneo con 2 n − 2 vértices contiene todo poliárbol con n vértices como subgrafo. ^{[ 11 ]}    

Una familia F de grafos tiene un grafo universal de tamaño polinomial, que contiene a cada grafo de n vértices como subgrafo inducido , si y solo si posee un esquema de etiquetado de adyacencia en el que los vértices pueden etiquetarse mediante cadenas de bits de O (log n )  bits, de manera que un algoritmo pueda determinar si dos vértices son adyacentes examinando sus etiquetas. Pues, si existe un grafo universal de este tipo, los vértices de cualquier grafo en F pueden etiquetarse con 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 con un vértice para cada etiqueta posible. ^{[ 12 ]}

En la terminología matemática antigua, la frase "grafo universal" se utilizaba a veces para referirse a un grafo completo .

La noción de grafo universal se ha adaptado y utilizado para resolver juegos de pago medio. ^{[ 13 ]}

• La fórmula panarborial , "Teorema del día" sobre grafos universales para árboles