Граф Генсона
Граф Генсона Gi — це неорієнтований нескінченний граф, єдиний зліченний однорідний граф, що не містить клік з i вершинами, але містить як підграфи всі вільні від Ki графи. Наприклад, G3 є графом без трикутників, що містить усі скінченні вільні від трикутників графи.
Графи названо ім'ям К. Ворда Генсона, який опублікував їх побудову 1971 року (для всіх )[1]. Перший із цих графів G3 називають однорідним вільним від трикутників графом або універсальним вільним від трикутників графом.
Для побудови цих графів Генсон упорядковує вершини графа Радо в послідовність із властивістю, що для будь-якої скінченної множини S вершин існує нескінченно багато вершин, що мають S як множину найраніших сусідів (існування такої послідовності єдиним чином визначає граф Радо). Потім він визначає Gi як породжений підграф графа Радо, утворений видаленням кінцевих вершин (у вибраному порядку) будь-якої i-кліки графа Радо[1].
За такої побудови будь-який граф Gi є породженим підграфом графа Gi + 1, а об'єднанням цього ланцюжка підграфів є сам граф Радо. Оскільки в будь-якому графі Gi виключено щонайменше одну вершину i-кліки графа Радо, в Gi не може бути i-клік.
Будь-який скінченний або зліченний вільний від i-клік граф H можна знайти як породжений підграф графа Gi послідовним додаванням вершин, раніші вершини яких у Gi відповідають множині раніших сусідів відповідних вершин в H. Таким чином, Gi є універсальним графом для сімейства вільних від i-клік графів.
Оскільки існують вільні від i-клік графи з довільно великим хроматичним числом, граф Генсона має нескінченне хроматичне число. Строгіше, якщо граф Генсона Gi розбити на будь-яке скінченне число породжених підграфів, то щонайменше один з цих графів включає всі вільні від i-клік скінченні графи як породжені підграфи[1].
Подібно до графа Радо, граф G3 містить двонаправлений гамільтонів шлях, такий, що будь-яка симетрія шляху є симетрією всього графа. Однак це не так для Gi, коли i > 3 — для цих графів будь-який автоморфізм графа має більше однієї орбіти[1].
- ↑ а б в г Henson, 1971, с. 69–83.
- C. Ward Henson. A family of countable homogeneous graphs // Pacific Journal of Mathematics. — 1971. — Т. 38 (13 листопада). — С. 69–83. — DOI:.