Граф Генсона

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

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

Побудова

Для побудови цих графів Генсон упорядковує вершини графа Радо в послідовність із властивістю, що для будь-якої скінченної множини Шаблон:Mvar вершин існує нескінченно багато вершин, що мають Шаблон:Mvar як множину найраніших сусідів (існування такої послідовності єдиним чином визначає граф Радо). Потім він визначає Шаблон:Math як породжений підграф графа Радо, утворений видаленням кінцевих вершин (у вибраному порядку) будь-якої Шаблон:Mvar-кліки графа РадоШаблон:Sfn.

За такої побудови будь-який граф Шаблон:Math є породженим підграфом графа Шаблон:Math, а об'єднанням цього ланцюжка підграфів є сам граф Радо. Оскільки в будь-якому графі Шаблон:Math виключено щонайменше одну вершину Шаблон:Mvar-кліки графа Радо, в Шаблон:Math не може бути Шаблон:Mvar-клік.

Універсальність

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

Оскільки існують вільні від Шаблон:Mvar-клік графи з довільно великим хроматичним числом, граф Генсона має нескінченне хроматичне число. Строгіше, якщо граф Генсона Шаблон:Math розбити на будь-яке скінченне число породжених підграфів, то щонайменше один з цих графів включає всі вільні від Шаблон:Mvar-клік скінченні графи як породжені підграфиШаблон:Sfn.

Симетрія

Подібно до графа Радо, граф Шаблон:Math містить двонаправлений гамільтонів шлях, такий, що будь-яка симетрія шляху є симетрією всього графа. Однак це не так для Шаблон:Math, коли Шаблон:Math — для цих графів будь-який автоморфізм графа має більше однієї орбітиШаблон:Sfn.

Література

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