гипотеза Альбертсона

Связь между раскраской графа и пересечениями

Нерешенная задача по математике :

Имеют ли полные графы наименьшее возможное число пересечений среди графов с тем же хроматическим числом ?

(еще нерешенные проблемы по математике)

Полный граф, нарисованный с тремя перекрестками, наименьшее число перекрестков среди всех графов, требующих шести цветов. ${\displaystyle K_{6}}$

В комбинаторной математике гипотеза Альбертсона — это недоказанная связь между числом пересечений и хроматическим числом графа . Она названа в честь Майкла О. Альбертсона, профессора колледжа Смита , который выдвинул ее в качестве гипотезы в 2007 году; ^[1] это одна из его многочисленных гипотез в теории раскраски графов . ^[2] Гипотеза утверждает, что среди всех графов, требующих цветов, полный граф — это граф с наименьшим числом пересечений. Эквивалентно, если граф можно нарисовать с меньшим числом пересечений, чем , то, согласно гипотезе, его можно раскрасить меньшим числом цветов. ${\displaystyle n}$ ${\displaystyle K_{n}}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$

Предполагаемая формула для минимального числа пересечений

Несложно показать, что графы с ограниченным числом пересечений имеют ограниченное хроматическое число: можно назначить различные цвета конечным точкам всех пересекающихся ребер, а затем раскрасить оставшийся планарный граф в 4 цвета . Гипотеза Альбертсона заменяет эту качественную связь между числом пересечений и раскраской более точной количественной связью. В частности, другая гипотеза Ричарда К. Гая  (1972) утверждает, что число пересечений полного графа равно ${\displaystyle K_{n}}$

${\displaystyle {\textrm {cr}}(K_{n})={\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }\left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor .}$

Известно, как нарисовать полные графы с таким количеством пересечений, помещая вершины в две концентрические окружности; неизвестно, существует ли лучший рисунок с меньшим количеством пересечений. Поэтому усиленная формулировка гипотезы Альбертсона заключается в том, что каждый -хроматический граф имеет число пересечений, по крайней мере, такое же большое, как правая часть этой формулы. ^[3] Эта усиленная гипотеза будет верна тогда и только тогда, когда верны как гипотеза Гая, так и гипотеза Альбертсона. ${\displaystyle n}$

Асимптотические границы

Более слабая форма гипотезы, доказанная М. Шефером ^[3], утверждает, что каждый граф с хроматическим числом имеет число пересечений (используя большую омега-нотацию ), или, что эквивалентно, каждый граф с числом пересечений имеет хроматическое число . Альбертсон, Крэнстон и Фокс (2009) опубликовали простое доказательство этих границ, объединив тот факт, что каждый минимальный -хроматический граф имеет минимальную степень по крайней мере  (потому что в противном случае жадная раскраска использовала бы меньше цветов) вместе с неравенством числа пересечений , согласно которому каждый граф с имеет число пересечений . Используя те же рассуждения, они показывают, что контрпример к гипотезе Альбертсона для хроматического числа (если он существует) должен иметь меньше вершин. ${\displaystyle n}$ ${\displaystyle \Omega (n^{4})}$ ${\displaystyle k}$ ${\displaystyle O(k^{1/4})}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle G=(V,E)}$ ${\displaystyle |E|/|V|\geq 4}$ ${\displaystyle \Omega (|E|^{3}/|V|^{2})}$ ${\displaystyle n}$ ${\displaystyle 4n}$

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

Гипотеза Альбертсона бессмысленно верна для . В этих случаях имеет число пересечений ноль, поэтому гипотеза утверждает только то, что -хроматические графы имеют число пересечений больше или равное нулю, что верно для всех графов. Случай гипотезы Альбертсона эквивалентен теореме о четырех цветах , что любой планарный граф может быть раскрашен четырьмя или менее цветами, поскольку единственными графами, требующими меньше пересечений, чем одно пересечение , являются планарные графы, и гипотеза подразумевает, что все они должны быть не более 4-хроматическими. Благодаря усилиям нескольких групп авторов гипотеза теперь известна как верная для всех . ^[4] Для каждого целого числа Луис и Рихтер представили семейство -цветокритических графов, которые не содержат подразделение полного графа , но имеют число пересечений не менее . ^[5] ${\displaystyle n\leq 4}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle n=5}$ ${\displaystyle K_{5}}$ ${\displaystyle n\leq 18}$ ${\displaystyle c\geq 6}$ ${\displaystyle (c+1)}$ ${\displaystyle K_{c+1}}$ ${\displaystyle K_{c+1}}$

Связанные предположения

Существует также связь с гипотезой Хадвигера , важной открытой проблемой в комбинаторике, касающейся связи между хроматическим числом и существованием больших клик как миноров в графе. ^[6] Вариант гипотезы Хадвигера, выдвинутый Дьёрдем Хайошем , состоит в том, что каждый -хроматический граф содержит подразделение ; если бы это было верно, то гипотеза Альбертсона следовала бы, поскольку число пересечений всего графа по крайней мере так же велико, как число пересечений любого из его подразделений. Однако теперь известны контрпримеры к гипотезе Хайоша, ^[7] поэтому эта связь не дает возможности для доказательства гипотезы Альбертсона. ${\displaystyle n}$ ${\displaystyle K_{n}}$

Примечания

1. По данным Альбертсона, Крэнстона и Фокса (2009), эта гипотеза была высказана Альбертсоном на специальной сессии Американского математического общества в Чикаго, состоявшейся в октябре 2007 года.
2. Хатчинсон, Джоан П. (19 июня 2009 г.), В память о Майкле О. Альбертсоне, 1946–2009: сборник его выдающихся гипотез и вопросов в теории графов (PDF) , Группа деятельности SIAM по дискретной математике.
3. Альбертсон, Крэнстон и Фокс (2009).
4. Опоровски и Чжао (2009); Альбертсон, Крэнстон и Фокс (2009); Барат и Тот (2010); Акерман (2019).
5. Луис и Рихтер (2014).
6. Барат и Тот (2010).
7. Кэтлин (1979); Эрдеш и Файтлович (1981).

Ссылки

• Акерман, Эяль (2019), «О топологических графах с максимум четырьмя пересечениями на ребро», Computational Geometry , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574, MR  4010251, S2CID  16847443
• Альбертсон, Майкл О.; Крэнстон, Дэниел В.; Фокс, Джейкоб (2009), «Раскраски, скрещивания и клики» (PDF) , Электронный журнал комбинаторики , 16 : R45, arXiv : 1006.3783 , Bibcode : 2010arXiv1006.3783A, doi : 10.37236/134, S2CID  8837711.
• Барат, Янош; Тот, Геза (2010), «К гипотезе Альбертсона», Электронный журнал комбинаторики , 17 (1): R73, arXiv : 0909.0413 , Bibcode : 2009arXiv0909.0413B, doi : 10.37236/345, S2CID  14640959.
• Кэтлин, П. А. (1979), «Гипотеза Хайоша о раскраске графов: вариации и контрпримеры», Журнал комбинаторной теории, Серия B , 26 (2): 268–274, doi : 10.1016/0095-8956(79)90062-5.
• Эрдеш, Пол ; Файтлович, Семион (1981), «О гипотезе Хайоса», Combinatorica , 1 (2): 141–143, doi : 10.1007/BF02579269, S2CID  1266711.
• Гай, Ричард К. (1972), «Числа пересечений графов», в Alavi, Y .; Lick, DR; White, AT (ред.), Теория графов и ее применение: Труды конференции в Университете Западного Мичигана, Каламазу, Мичиган, 10–13 мая 1972 г. , Нью-Йорк: Springer-Verlag, стр. 111–124. Как цитируют Альбертсон, Крэнстон и Фокс (2009).
• Oporowski, B.; Zhao, D. (2009), «Раскраска графов с пересечениями», Discrete Mathematics , 309 (9): 2948–2951, arXiv : math/0501427 , doi : 10.1016/j.disc.2008.07.040, S2CID  16497175.
• Луис, Атилио; Рихтер, Брюс (2014), «Замечания о гипотезе Барата и Тота», Электронный журнал комбинаторики , 21 (1): P1.57, doi : 10.37236/3396.