Interested Article - Граф Турана

Граф Турана T ( n , r ) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь $(n\,{\bmod {\,}}r)$ подмножеств размером $\lceil n/r\rceil$ и $r-(n\,{\bmod {\,}}r)$ подмножеств размером $\lfloor n/r\rfloor$ . Таким образом, это полный r -дольный граф

K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\ldots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.

Каждая вершина имеет степень либо $n-\lceil n/r\rceil$ , либо $n-\lfloor n/r\rfloor$ . Число рёбер равно

{\frac {1}{2}}(n^{2}-(n\,{\bmod {\,}}r)\lceil n/r\rceil ^{2}-(r-(n\,{\bmod {\,}}r))\lfloor n/r\rfloor ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}.

Граф является регулярным , если n делится на r .

Теорема Турана

Графы Турана названы в честь Пала Турана , использовавшего их для доказательства теоремы Турана , важного результата в экстремальной теории графов .

По принципу Дирихле , любое множество из r + 1 вершин в графе Турана включает две вершины из одной и той же доли графа. Таким образом, граф Турана не содержит клику размера r + 1. Согласно теореме Турана, граф Турана имеет максимально возможное число рёбер среди всех графов без клик размера r + 1, имеющих n вершин. Киваш и Судаков (Keevash, Sudakov, 2003) показали, что граф Турана является единственным графом без клик размера r + 1, имеющим порядок n , в котором любое подмножество из α n вершин имеет по меньшей мере ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$ рёбер, если α достаточно близко к 1. расширяет теорему Турана, ограничивая число рёбер в графе, не имеющем фиксированный граф Турана в качестве подграфа. Вследствие этой теоремы в теории экстремальных графов для любого запрещённого подграфа можно доказать похожие границы, зависящие от хроматического числа подграфа.

Особые случаи

Октаэдр, вершины и рёбра которого образуют граф Турана T (6,3).

Некоторые величины параметра r графов Турана приводят к замечательным графам, которые изучаются отдельно.

Граф Турана T (2 n , n ) можно получить удалением совершенного паросочетания из полного графа K _{2

n} . Как показал Робертс ( ), рамочность этого графа равна в точности n . Этот граф иногда называют графом Робертса . Этот граф является также 1- ^* n -мерного кографа . Например, граф T (6,3) = K _2,2,2 — это граф правильного октаэдра . Если n пар приходят на вечеринку и каждый человек пожимает руку всем, кроме своего партнёра, то данный граф описывает множество рукопожатий. По этой причине его также называют графом коктейль-вечеринки .

Граф Турана T ( n ,2) — это полный двудольный граф , и, если n чётно, это граф Мура . Если r — это делитель n , граф Турана является симметричным и сильно регулярным , хотя некоторые авторы считают, что графы Турана являются тривиальным случаем сильной регулярности и потому исключают их из определения строго регулярных графов.

Граф Турана $T(n,\lceil n/3\rceil )$ имеет 3 ^a 2 ^b наибольших клик , где 3 a + 2 b = n и b ≤ 2. Каждая наибольшая клика образуется выбором одной вершины из каждой доли. Это число наибольших клик является наибольшим возможным среди всех графов с n вершинами, независимо от числа рёбер в графе (Мун и Мозер, 1965). Эти графы иногда называют графами Муна-Мозера .

Другие свойства

Любой граф Турана является кографом . Таким образом, его можно образовать из отдельных вершин последовательностью операций дизъюнктного объединения и дополнения . В частности, такую последовательность можно начать образованием всех независимых множеств графа Турана как дизъюнктного объединения изолированных вершин. Тогда весь граф является дополнением дизъюнктного объединения дополнений этих независимых множеств.

Чао и Новацки (Chao, Novacky, 1982) показали, что графы Турана хроматически единственны — никакие другие графы не имеют те же самые хроматические многочлены . Никифоров (Nikiforov, 2005) использовал графы Турана для нахождения нижней границы суммы k -х собственных значений графа и его дополнения.

Фолс, Повел и Снойинк (Falls, Powell, Snoeyink) разработали эффективный алгоритм для поиска кластеров ортологических групп генов в геноме путём представления данных как графа и поиска больших подграфов Турана.

Графы Турана имеют также ряд интересных свойств, связанных с . Пор и Вуд (Pór, Wood, 2005) дают нижнюю границу Ω(( rn ) ^3/4 ) любого трёхмерного вложения графа Турана. Витсенхаузен (Witsenhausen, 1974) высказал гипотезу, что максимальная сумма квадратов расстояний между n точками внутри шара в R ^d единичного диаметра достигается на конфигурации, образованной вложению графа Турана в вершины правильного симплекса.

Граф G с n вершинами является подграфом графа Турана T ( n , r ) тогда и только тогда, когда G допускает справедливую раскраску в r цветов. Разложение графа Турана на независимые множества соответствует разложению G на классы цветов. В частности, граф Турана является единственным максимальным графом с n вершинами со справедливой раскраской в r цветов.

Примечания

Литература

C. Y. Chao, G. A. Novacky. On maximally saturated graphs // Discrete Mathematics. — 1982. — Т. 41 , вып. 2 . — С. 139–143 . — doi : .
Craig Falls, Bradford Powell, Jack Snoeyink. Computing high-stringency COGs using Turán type graphs.
Peter Keevash, Benny Sudakov. Local density in graphs with forbidden subgraphs // Combinatorics, Probability and Computing. — 2003. — Т. 12 , вып. 2 . — С. 139–153 . — doi : .
J. W. Moon, L. Moser. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3 . — С. 23–28 . — doi : .
Vladimir Nikiforov. . — 2005. — arXiv : .
Attila Pór, David R Wood. . — Lecture Notes in Computer Science no. 3383, Springer-Verlag, 2005. — С. 395–402. — doi : .
F. S. Roberts. Recent Progress in Combinatorics. — Academic Press, 1969. — С. 301–310.
P. Turán. On an extremal problem in graph theory // Matematiko Fizicki Lapok. — 1941. — Т. 48 . — С. 436–452 .
H. S. Witsenhausen. // American Mathematical Monthly . — The American Mathematical Monthly, Vol. 81, No. 10, 1974. — Т. 81 , вып. 10 . — С. 1100–1101 . — doi : . — JSTOR .