Граф Хэнсона

Граф Хэнсона Шаблон:Math — это неориентированный бесконечный граф, единственный счётный однородный граф, не содержащий клики с Шаблон:Mvar вершинами, но содержащий в качестве подграфов все свободные от Шаблон:Mvar графы. Например, Шаблон:Math является графом без треугольников, содержащим все конечные свободные от треугольников графы.

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

Построение

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

При таком построении любой граф Шаблон:Math является порождённым подграфом графа Шаблон:Math, а объединением этой цепочки подграфов является сам граф Радо. Поскольку в любом графе Шаблон:Math исключена по меньшей мере одна вершина Шаблон:Mvar-клики графа Радо, в Шаблон:Math не может быть Шаблон:Mvar-клик.

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

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

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

Симметрия

Подобно графу Радо граф Шаблон:Math содержит двунаправленный гамильтонов путь, такой, что любая симметрия пути является симметрией всего графа. Однако это не верно для Шаблон:Math, когда Шаблон:Math — для этих графов любой автоморфизм графа имеет более одной орбитыШаблон:Sfn.

Литература

• Шаблон:Статья