Граф Хэнсона

Граф Хэнсона G_i — это неориентированный бесконечный граф, единственный счётный однородный граф, не содержащий клики с i вершинами, но содержащий в качестве подграфов все свободные от K_i графы. Например, G₃ является графом без треугольников, содержащим все конечные свободные от треугольников графы.

Графы названы именем К. Уорда Хэнсона, опубликовавшим их построение в 1971 (для всех $i\geqslant 3$). Первый из этих графов G₃ называется однородным свободным от треугольников графом или универсальным свободным от треугольников графом.

Построение

Для построения этих графов Хэнсон упорядочивает вершины графа Радо в последовательность со свойством, что для любого конечного множества S вершин существует бесконечное много вершин, имеющих S в качестве множества самых ранних соседей (cуществование такой последовательности единственным образом определяет граф Радо). Затем он определяет G_i как порождённый подграф графа Радо, образованный удалением конечных вершин (в выбранном порядке) любой i-клики графа Радо.

При таком построении любой граф G_i является порождённым подграфом графа G_{i + 1}, а объединением этой цепочки подграфов является сам граф Радо. Поскольку в любом графе G_i исключена по меньшей мере одна вершина i-клики графа Радо, в G_i не может быть i-клик.

Универсальность

Любой конечный или счётный свободный от i-клик граф H можно найти как порождённый подграф графа G_i путём последовательного добавления вершин, более ранние вершины которых в G_i соответствуют множеству более ранних соседей соответствующих вершин в H. Таким образом, G_i является универсальным графом для семейства свободных от i-кликов графов.

Поскольку существуют свободные от i-клик графы с произвольно большим хроматическим числом, граф Хэнсона имеет бесконечное хроматическое число. Более строго, если граф Хэнсона G_i разбить на любое конечное число порождённых подграфов, то по меньшей мере один из этих графов включает все свободные от i-клик конечные графы в качестве порождённых подграфов.

Симметрия

Подобно графу Радо граф G₃ содержит двунаправленный гамильтонов путь, такой, что любая симметрия пути является симметрией всего графа. Однако это не верно для G_i, когда i > 3 — для этих графов любой автоморфизм графа имеет более одной орбиты.