Теорема Фрухта

Теорема Фрухта є теоремою в алгебричній теорії графів, висловленої в 1936 році Денешем Кенігом і доведеною Робертом Фрухтом в 1939 році. Вона стверджує, що будь-яку скінченну групу можна представити, як групу симетрій скінченного неорієнтованого графу. Більше того, для будь-якої скінченної групи G існує нескінченно багато неізоморфних простих зв'язних графів, для яких група автоморфізму кожного з них ізоморфна G.

Граф Фрухта, 3-регулярний граф, група автоморфізму якого реалізує тривіальну групу.

Доведення

Доведення полягає в тому, що граф Келі G, з додаванням кольорів і орієнтацій на його ребрах, має бажану групу автоморфізму. Тому, якщо кожне з цих ребер замінено на відповідний субграф, так що кожний підграф заміни асиметричний, а дві заміни ізоморфні тоді і тільки тоді, коли вони замінюють ребра одного кольору, то неорієнтований граф, створений за допомогою цих замін, також буде мати G як свою групу симетрії.

Розмір графа

За винятком трьох циклічних груп (порядків 3, 4 і 5) — кожну групу можна представити як симетрію графа, вершини якого мають лише дві орбіти.

Спеціальні види графів

Існують інші інтерпретації теореми Фрухта, які показують, що деякі обмежені види графів все ще містять достатньо графів для реалізації будь-якої групи симетрії. Наприклад, граф Фрухта, 3-регулярний граф з 12 вершинами і 18 ребрами, не має нетривіальних симетрій, що забезпечує реалізацію цього типу для тривіальної групи. З того факту, що кожен граф може бути реконструйований з часткової множини впорядкування його ребер і вершин, то кожен кінцевий порядок еквівалентний теоремі Біркгофа про скінченну розподільну решітку, кожна група може бути реалізована як дистрибутивна ґратка, а граф ґратки- медіанний граф. Кожну скінченну групу можна реалізувати як групу симетрій сильно регулярного графа. Кожну скінченну групу також можна реалізувати як симетрії графа з числом 2: можна (неправильно) розфарбувати граф двома кольорами, щоб жодна з симетрій графа не зберегла забарвлення.

Проте деякі важливі класи графів не здатні реалізувати всі групи як свої симетрії. Каміль Жордан охарактеризував групи симетрії дерев як найменшу сукупність скінченних груп, що є тривіальними групами. У загальному випадку, будь-яка група графів з замкнутою структурою не здатна представити всі скінченні групи симетріями її графів.

Джерела

• de Groot, J. (1959), Groups represented by homeomorphism groups, Mathematische Annalen, 138: 80—102, doi:10.1007/BF01369667, ISSN 0025-5831, MR 0119193.
• Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen, Leipzig: Akademische Verlagsgesellschaft, с. 5. As cited by Babai, (1995).
• Sabidussi, Gert (1957), Graphs with given group and given graph-theoretical properties, Canadian Journal of Mathematics, 9: 515—525, doi:10.4153/cjm-1957-060-7, ISSN 0008-414X, MR 0094810, архів оригіналу за 16 липня 2011, процитовано 27 січня 2019.