Gráfico de Henson

En teoría de grafos , el grafo de Henson G _i es un grafo infinito no dirigido , el único grafo homogéneo numerable que no contiene una camarilla de i vértices , pero que sí contiene todos los grafos finitos libres de K _i como subgrafos inducidos. Por ejemplo, G ₃ es un grafo libre de triángulos que contiene todos los grafos finitos libres de triángulos.

Estos grafos reciben su nombre de C. Ward Henson, quien publicó una construcción para ellos (para todo i ≥ 3 ) en 1971. ^{[ 1 ]} El primero de estos grafos, G ₃ , también se denomina grafo homogéneo libre de triángulos o grafo universal libre de triángulos .

Para construir estos grafos, Henson ordena los vértices del grafo de Rado en una secuencia con la propiedad de que, para cada conjunto finito S de vértices, existen infinitos vértices que tienen a S como su conjunto de vecinos anteriores. (Solo el grafo de Rado posee dicha secuencia). A continuación, define G _i como el subgrafo inducido del grafo de Rado formado al eliminar el último vértice (en el ordenamiento de la secuencia) de cada i -clique del grafo de Rado. ^{[ 1 ]}

Con esta construcción, cada grafo G _i es un subgrafo inducido de G _{i + 1} , y la unión de esta cadena de subgrafos inducidos es el propio grafo de Rado. Debido a que cada grafo G _i omite al menos un vértice de cada i -clique del grafo de Rado, no puede haber i- clique en G _i .

Cualquier grafo H, finito o numerable y libre de i -cliques, puede encontrarse como un subgrafo inducido de G _i construyéndolo vértice a vértice, añadiendo en cada paso un vértice cuyos vecinos anteriores en G _i coincidan con el conjunto de vecinos anteriores del vértice correspondiente en H. Es decir, G _i es un grafo universal para la familia de grafos libres de i -cliques.

Debido a que existen grafos libres de i -cliques con un número cromático arbitrariamente grande , los grafos de Henson tienen un número cromático infinito. Más aún, si un grafo de Henson G _i se particiona en cualquier número finito de subgrafos inducidos, entonces al menos uno de estos subgrafos incluye todos los grafos finitos libres de i -cliques como subgrafos inducidos. ^{[ 1 ]}

Al igual que el grafo de Rado, G ₃ contiene un camino hamiltoniano bidireccional tal que cualquier simetría del camino es una simetría de todo el grafo. Sin embargo, esto no es cierto para G _i cuando i > 3 : para estos grafos, cada automorfismo del grafo tiene más de una órbita. ^{[ 1 ]}