Теорема фрухта является теорема в алгебраической теории графов высказал предположение по Dénes Konig в 1936 году [1] и доказал Роберт Фрухта в 1939 году [2] Он утверждает , что любая конечная группа является группой симметрий конечного неориентированного графа . Сильнее, для любой конечной группы G существует бесконечное множество неизоморфных простых связных графов таких , что группа автоморфизмов каждого из них изоморфны в G .
Доказательство идеи
Основная идея доказательства состоит в том, чтобы заметить, что граф Кэли группы G с добавлением цветов и ориентаций на его ребрах, чтобы отличать образующие G друг от друга, имеет желаемую группу автоморфизмов. Следовательно, если каждое из этих ребер заменяется соответствующим подграфом, так что каждый замещающий подграф сам является асимметричным, а две замены изоморфны тогда и только тогда, когда они заменяют ребра одного цвета, тогда неориентированный граф, созданный посредством выполнения этих замен, также будет есть G в качестве группы симметрии. [3]
Размер графика
За тремя исключениями - циклическими группами порядков 3, 4 и 5 - каждую группу можно представить как симметрии графа, вершины которого имеют только две орбиты . Следовательно, количество вершин в графе не более чем в два раза превышает порядок группы. За большим набором исключений большинство конечных групп могут быть представлены как симметрии вершинно-транзитивного графа с числом вершин, равным порядку группы. [4]
Специальные семейства графов
Существуют более сильные версии теоремы Фрухта, которые показывают, что некоторые ограниченные семейства графов все еще содержат достаточно графов для реализации любой группы симметрии. Фрухт [5] доказал, что на самом деле существует счетное число 3-регулярных графов с требуемым свойством; например, граф Фрухта , 3-регулярный граф с 12 вершинами и 18 ребрами, не имеет нетривиальных симметрий, обеспечивая реализацию этого типа для тривиальной группы . Герт Сабидусси показал, что любая группа может быть реализована как группы симметрии счетного числа различных k - регулярных графов , графов с k- вершинной связью или k -хроматических графов для всех положительных целых значений k (с для регулярных графиков и для k -хроматических графов). [6] Из того факта, что любой граф может быть восстановлен по частичному порядку включения его ребер и вершин, что каждый конечный частичный порядок эквивалентен по теореме Биркгофа о представлении конечной дистрибутивной решетке , следует, что любая конечная группа может быть реализована как симметрии дистрибутивной решетки и графа решетки, медианного графа . [3] Любую конечную группу можно реализовать как группу симметрий сильно регулярного графа . [7] Каждая конечная группа также может быть реализована как симметрия графа с отличительным номером два: можно (неправильно) раскрасить граф в два цвета так, чтобы ни одна из симметрий графа не сохраняла раскраску. [8]
Однако некоторые важные классы графов не могут реализовать все группы как свои симметрии. Камилла Джордан охарактеризовала группы симметрий деревьев как наименьшее множество конечных групп, содержащих тривиальную группу и замкнутых относительно прямых произведений друг на друга и сплетений с симметрическими группами ; [9], в частности, циклическая группа третьего порядка не является группой симметрии дерева. Плоские графы также не могут реализовать все группы как свои симметрии; например, единственными конечными простыми группами, которые являются симметриями плоских графов, являются циклические группы и знакопеременная группа . [10] В более общем смысле, любое семейство минорно-замкнутых графов не способно представить все конечные группы симметриями своих графов. [11] Ласло Бабай высказывает более сильную гипотезу о том, что каждое минорно-замкнутое семейство может представлять только конечное число нециклических конечных простых групп. [12]
Бесконечные графы и группы
Избицкий расширил эти результаты в 1959 году и показал, что существует несчетное количество бесконечных графов, реализующих любую конечную группу симметрии. [13] Наконец, Йоханнес де Гроот и Сабидусси в 1959/1960 независимо доказали, что любая группа (отказавшись от предположения, что группа конечна) может быть реализована как группа симметрий бесконечного графа. [14] [15]
Рекомендации
- ^ Кёнига (1936)
- ^ Frucht (1939)
- ^ a b Бабай (1995) , обсуждение после теоремы 4.1.
- Перейти ↑ Babai (1995) , раздел 4.3.
- ^ Frucht (1949)
- ^ Сабидусси (1957)
- ^ Бабай (1995) , теорема 4.3.
- ^ Альбертсон, Майкл O .; Коллинз, Карен Л. (1996), «Нарушение симметрии в графах» , Электронный журнал комбинаторики , 3 (1): R18, MR 1394549.
- Перейти ↑ Babai (1995) , Proposition 1.15. Бабай датирует результат Иордании 1869 годом, но включает в свою библиографию только статью Иордании 1895 года.
- ^ Бабай (1995) , обсуждение после теоремы 1.17.
- ^ Бабай (1995) , теорема 4.5.
- ^ Бабай (1995) , обсуждение после теоремы 4.5.
- ^ Izbicki (1959)
- ^ де Гроот (1959)
- ^ Сабидусси (1960)
Источники
- Бабай, Ласло (1995), "Группы автоморфизмов, изоморфизм, реконструкция" (PDF) , в Graham, Ronald L .; Грёчель, Мартин ; Ловас, Ласло (ред.), Справочник по комбинаторике , I , Северная Голландия, стр. 1447–1540..
- де Гроот, Johannes (1959), "Группы представлены гомеоморфизм группы", Mathematische Annalen , 138 : 80-102, DOI : 10.1007 / BF01369667 , ЛВП : 10338.dmlcz / 101909 , ISSN 0025-5831 , MR 0119193.
- Фрухт, Роберт (1939), «Herstellung von Graphen mit vorgegebener abstrakter Gruppe». , Compositio Mathematica (на немецком языке), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804.
- Frucht, Роберт (1949), "Графы третьей степени с данной абстрактной группы" , Canadian Journal математики , 1 (4): 365-378, DOI : 10,4153 / CJM-1949-033-6 , ISSN 0008-414X , Руководство по ремонту 0032987.
- Izbicki, Herbert (1959), "endlichen сортов Unendliche графена мит vorgegebenen Eigenschaften", Ежемесячник für Mathematik , 63 (3): 298-301, DOI : 10.1007 / BF01295203 , МР 0105372.
- Kőnig, Dénes (1936), Theorie der endlichen und unendlichen Graphen , Лейпциг : Akademische Verlagsgesellschaft, стр. 5. Цитируется Бабаем (1995) .
- Сабидусси, Герт (1957), "Графы с данной группой и данный граф-теоретический свойств" , Canadian Journal математики , 9 : 515-525, DOI : 10,4153 / CJM-1957-060-7 , ISSN 0008-414X , МР 0094810.
- Сабидусси, Герт (1960), "Графы с данной бесконечной группой", Ежемесячник für Mathematik , 64 : 64-67, DOI : 10.1007 / BF01319053 , МР 0115935.