Граф Тутта–Коксетера

3-регулярный граф с 30 вершинами и 45 ребрами

В математической области теории графов граф Тутта –Коксетера или граф Кремоны – Ричмонда — это 3- регулярный граф с 30 вершинами и 45 ребрами. Как уникальный наименьший кубический граф с обхватом 8, он является клеткой и графом Мура . Он является двудольным и может быть построен как граф Леви обобщенного четырехугольника W ₂ (известного как конфигурация Кремоны–Ричмонда ). Граф назван в честь Уильяма Томаса Тутта и Х. С. М. Коксетера ; он был открыт Туттом (1947), но его связь с геометрическими конфигурациями была исследована обоими авторами в паре совместно опубликованных статей (Тутт 1958; Коксетер 1958a).

Все кубические дистанционно-регулярные графы известны. ^[1] Граф Тутта–Коксетера является одним из 13 таких графов.

Он имеет номер пересечения 13, ^{[2] [3]} толщину книги 3 и номер очереди 2. ^[4]

Конструкции и автоморфизмы

Граф Тутта–Коксетера — это двудольный граф Леви, соединяющий 15 совершенных паросочетаний 6-вершинного полного графа K ₆ с его 15 ребрами, как описано Коксетером (1958b) на основе работы Сильвестра (1844). Каждая вершина соответствует ребру или совершенному паросочетанию, а соединенные вершины представляют структуру инцидентности между ребрами и паросочетаниями.

Основываясь на этой конструкции, Коксетер показал, что граф Тутта–Коксетера является симметричным графом ; он имеет группу из 1440 автоморфизмов , которые можно отождествить с автоморфизмами группы перестановок на шести элементах (Коксетер 1958b). Внутренние автоморфизмы этой группы соответствуют перестановке шести вершин графа K ₆ ; эти перестановки действуют на граф Тутта–Коксетера, переставляя вершины на каждой стороне его двудольного разбиения, сохраняя при этом каждую из двух сторон фиксированной как набор. Кроме того, внешние автоморфизмы группы перестановок меняют одну сторону двудольного разбиения на другую. Как показал Коксетер, любой путь из пяти ребер в графе Тутта–Коксетера эквивалентен любому другому такому пути одним таким автоморфизмом.

Граф Тутта–Коксетера как здание

Этот граф является сферическим зданием, связанным с симплектической группой (между этой группой и симметрической группой существует исключительный изоморфизм ). Более конкретно, это граф инцидентности обобщенного четырехугольника . ${\displaystyle Sp_{4}(\mathbb {F} _{2})}$ ${\displaystyle S_{6}}$

Конкретно, граф Тутта-Коксетера можно определить из 4-мерного симплектического векторного пространства следующим образом: ${\displaystyle V}$ ${\displaystyle \mathbb {F} _{2}}$

• вершины — это либо ненулевые векторы, либо изотропные 2-мерные подпространства,
• существует ребро между ненулевым вектором v и изотропным 2-мерным подпространством тогда и только тогда, когда . ${\displaystyle W\subset V}$ ${\displaystyle v\in W}$

Галерея

• 
  Хроматическое число графа Тутта–Коксетера равно 2.
• 
  Хроматический индекс графа Тутта–Коксетера равен 3.

Ссылки

1. Брауэр, А.Э.; Коэн, AM; и Ноймайер А. Дистанционно-регулярные графы. Нью-Йорк: Springer-Verlag, 1989.
2. Пегг, ET ; Эксо, G. (2009). «Пересечение числовых графов». Журнал Mathematica . 11 (2). doi : 10.3888/tmj.11.2-2 .
3. Эксо, Г. «Прямолинейные рисунки известных графиков».
4. Вольц, Джессика; Проектирование линейных макетов с SAT. Магистерская работа, Тюбингенский университет, 2018 г.

• Коксетер, HSM (1958a). «Хорды ​​нелинейчатой ​​квадрики в PG(3,3)». Can. J. Math . 10 : 484–488. doi : 10.4153/CJM-1958-047-0 .
• Coxeter, HSM (1958b). «Двенадцать точек в PG(5,3) с 95040 самопреобразованиями». Труды Королевского общества A. 247 ( 1250): 279–293. Bibcode : 1958RSPSA.247..279C. doi : 10.1098/rspa.1958.0184. JSTOR  100667. S2CID  121676627.
• Сильвестр, Дж. Дж. (1844). «Элементарные исследования в анализе комбинаторной агрегации». Phil. Mag . Series 3. 24 : 285–295. doi :10.1080/14786444408644856.
• Tutte, WT (1947). «Семейство кубических графов». Proc. Cambridge Philos. Soc . 43 (4): 459–474. Bibcode : 1947PCPS...43..459T. doi : 10.1017/S0305004100023720. S2CID  123505185.
• Tutte, WT (1958). «Хорды ​​нелинейчатой ​​квадрики в PG(3,3)». Can. J. Math . 10 : 481–483. doi : 10.4153/CJM-1958-046-3 .

Внешние ссылки

• Франсуа Лабель. «3D-модель 8-клетки Тутте».
• Вайсштейн, Эрик В. «Граф Леви». MathWorld .
• Эксоо, Г. «Прямолинейные рисунки известных графиков». [1]