Теорема Фрухтса - Fruchts theorem

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

Теорема Фрухта это теорема в алгебраическая теория графов предположено Денес Кёниг в 1936 г.[1] и доказано Роберт Фрухт в 1939 г.[2] В нем говорится, что каждый конечный группа это группа симметрии конечного неориентированный граф. Более того, для любого конечного группа грамм существует бесконечно много неизоморфный просто связанные графы так что группа автоморфизмов каждого из них изоморфный кграмм.

Доказательство идеи

Основная идея доказательства состоит в том, чтобы заметить, что Граф Кэли из грамм, с добавлением цветов и ориентаций на его краях, чтобы различать образующие грамм друг от друга, имеет желаемую группу автоморфизмов. Следовательно, если каждое из этих ребер заменяется соответствующим подграфом, так что каждый замещающий подграф сам является асимметричным, а две замены изоморфны тогда и только тогда, когда они заменяют ребра одного цвета, тогда неориентированный граф, созданный посредством выполнения этих замен, также будет имеют грамм как его группа симметрии.[3]

Размер графика

За тремя исключениями - циклическими группами порядков 3, 4 и 5 - каждую группу можно представить как симметрии графа, вершины которого имеют только две орбиты. Следовательно, количество вершин в графе не более чем в два раза превышает порядок группы. За большим набором исключений большинство конечных групп можно представить как симметрии вершинно-транзитивный граф, с числом вершин, равным порядку группы.[4]

Специальные семейства графов

Существуют более сильные версии теоремы Фрухта, которые показывают, что некоторые ограниченные семейства графов все еще содержат достаточно графов для реализации любой группы симметрии. Frucht[5] доказал, что на самом деле счетное множество 3-регулярные графы с желаемой собственностью есть; например, Граф Фрухта, 3-регулярный граф с 12 вершинами и 18 ребрами, не имеет нетривиальных симметрий, обеспечивая реализацию этого типа для тривиальная группа. Герт Сабидусси показал, что любую группу можно реализовать как группы симметрии счетного числа различных k-регулярные графики, k-связные графы, или же k-хроматические графики, для всех положительных целых значений k (с для регулярных графиков и за k-хроматические графики).[6] Из того факта, что каждый граф может быть восстановлен из содержания частичный заказ его ребер и вершин, что каждый конечный частичный порядок эквивалентен Теорема Биркгофа о представлении к конечному распределительная решетка, следует, что всякая конечная группа может быть реализована как симметрии дистрибутивной решетки и графика решетки a медианный график.[3] Любую конечную группу можно реализовать как группу симметрий сильно регулярный граф.[7] Каждая конечная группа также может быть реализована как симметрия графа с отличительный номер два: можно (неправильно) раскрасить граф в два цвета, чтобы ни одна из симметрий графа не сохранила раскраску.[8]

Однако некоторые важные классы графов не могут реализовать все группы как свои симметрии. Камилла Джордан охарактеризовал группы симметрии деревья как наименьшее множество конечных групп, содержащих тривиальная группа и закрыт под прямые продукты друг с другом и венки с симметричные группы;[9] в частности, циклическая группа третьего порядка не является группой симметрии дерева. Планарные графики также не способны реализовать все группы как свои симметрии; например, единственный конечные простые группы симметрии плоских графов циклические группы и переменная группа .[10] В более общем плане каждый семейство минорных замкнутых графов не может представить все конечные группы симметриями своих графов.[11] Ласло Бабай более сильные гипотезы о том, что каждое минорно-замкнутое семейство может представлять только конечное число нециклических конечных простых групп.[12]

Бесконечные графы и группы

Избицкий расширил эти результаты в 1959 г. и показал, что бесчисленное множество бесконечный графы, реализующие любую конечную группу симметрий.[13] Ну наконец то, Йоханнес де Гроот и Сабидусси в 1959/1960 независимо доказали, что любая группа (отказавшись от предположения, что группа конечна) может быть реализована как группа симметрий бесконечного графа.[14][15]

Рекомендации

  1. ^ Кениг (1936)
  2. ^ Фрухт (1939)
  3. ^ а б Бабай (1995), обсуждение после теоремы 4.1.
  4. ^ Бабай (1995), Раздел 4.3.
  5. ^ Фрухт (1949)
  6. ^ Сабидусси (1957)
  7. ^ Бабай (1995), Теорема 4.3.
  8. ^ Альбертсон, Майкл О .; Коллинз, Карен Л. (1996), «Нарушение симметрии в графах», Электронный журнал комбинаторики, 3 (1): R18, МИСТЕР  1394549.
  9. ^ Бабай (1995), Предложение 1.15. Бабай датирует результат Иордании 1869 годом, но включает в свою библиографию только статью Иордании 1895 года.
  10. ^ Бабай (1995), обсуждение после теоремы 1.17.
  11. ^ Бабай (1995), Теорема 4.5.
  12. ^ Бабай (1995), обсуждение после теоремы 4.5.
  13. ^ Избицкий (1959)
  14. ^ де Гроот (1959)
  15. ^ Сабидусси (1960)

Источники