Граф Татта — Коксетера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Татта — Коксетера
Изображение
Назван в честь

Уильям Татт[en]
Гарольд Коксетер

Вершин

30

Рёбер

45

Диаметр

4

Обхват

8

Автоморфизмы

1440 (Aut(S6))

Хроматическое число

2

Хроматический индекс

3

Свойства

кубический
Симметричный
клетка
граф Мура[en]
дистанционно-регулярный
дистанционно-транзитивный

Граф Татта — Коксетера (также 8-клетка Татта) — 3-регулярный граф с 30 вершинами и 45 рёбрами. Являясь единственным наименьшим кубическим графом с обхватом 8, граф является клеткой и графом Мура[en]. Он является двудольным и может быть построен как граф Леви обобщённого четырёхугольника[en] W2 (известного как конфигурация Кремона — Ричмонда). Граф назван в честь Уильяма Томаса Татта (англ. William Thomas Tutte) и Гарольда Коксетера. Граф был найден Уильямом Таттом (Tutte 1947), но его связь с геометрической комбинацией была исследована обоими авторами в паре совместных статей (Tutte 1958, Coxeter (a) 1958).

Является одним из тринадцати кубических дистанционно-регулярных графов[1].

Двойки, наборы и автоморфизмы[править | править вики-текст]

Особенно простое комбинаторное построение графа Татта — Коксетера предложено Коксетером (Coxeter (b) 1958), которое основывается на ранних работах Сильвестра (Sylvester 1844). Образуем множество из шести элементов (например, это буквы a, b, c, d, e, f). Сильвестер определил двойки как 15 неупорядоченных пар элементов: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, or ef. Он также определил наборы — разбиения элементов на три двойки: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, be, df); (ac, bf, de); (ad, bc, ef); (ad, be, cf); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Каждый набор содержит три двойки, и каждая двойка принадлежит трём наборам. Граф Татта — Коксетера можно рассматривать как граф, в котором каждая вершина соответствует двойке, а также набору двоек — по вершине для каждого набора, и рёбра соединяют каждый набор с тремя двойками, содержащихся в нём.

Основываясь на этом построении, Коксетер показал, что граф Татта — Коксетера является симметричным. Он имеет 1440 автоморфизмов графа, которые можно отождествить с автоморфизмами группы перестановок шести элементов (Coxeter (b) 1958). Внутренние автоморфизмы этой группы соответствуют перестановкам шести элементов, из которых определяем морфемы и наборы. Эти перестановки действуют на граф Татта — Коксетера путём перестановок вершин на каждой доле двудольного графа, сохранная каждую долю как множество. Вдобавок, внешние автоморфизмы[en] группы перестановок переставляют местами доли двудольного графа. Как показал Коксетер, любой путь длиной до пяти рёбер графа Татта — Коксетера эквивалентен любому другому такому пути (то есть переводятся из одного в другой с помощью одного из таких автоморфизмов).

Галерея[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.

Литература[править | править вики-текст]

  • H. S. M. Coxeter The chords of the non-ruled quadric in PG(3,3) // Canad. J. Math.. — 1958. — Т. 10. — С. 484–488. — DOI:10.4153/CJM-1958-047-0
  • J. J. Sylvester Elementary researches in the analysis of combinatorial aggregation // The Philos. Mag., Series 3. — 1844. — Т. 24. — С. 285–295.
  • W. T. Tutte A family of cubical graphs // Proc. Cambridge Philos. Soc.. — 1947. — В. 04. — Т. 43. — С. 459–474. — DOI:10.1017/S0305004100023720
  • W. T. Tutte The chords of the non-ruled quadric in PG(3,3) // Canad. J. Math.. — 1958. — Т. 10. — С. 481–483. — DOI:10.4153/CJM-1958-046-3

Ссылки[править | править вики-текст]