Граф Генсона

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

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

Побудова

Для побудови цих графів Генсон упорядковує вершини графа Радо в послідовність із властивістю, що для будь-якої скінченної множини S вершин існує нескінченно багато вершин, що мають S як множину найраніших сусідів (існування такої послідовності єдиним чином визначає граф Радо). Потім він визначає 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 — для цих графів будь-який автоморфізм графа має більше однієї орбіти.

Література

• C. Ward Henson. A family of countable homogeneous graphs // Pacific Journal of Mathematics. — 1971. — Т. 38 (13 листопада). — С. 69–83. — DOI:10.2140/pjm.1971.38.69.