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

Шаблон:Unsolved Гипотеза Албертсона — недоказанная связь между числом пересечением и хроматическим числом графа. Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит, который сформулировал утверждение в качестве гипотезы в 2007. Гипотеза является одной из многих гипотез в теории раскраски графовШаблон:Sfn. Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф K_n находится среди графов, имеющих наименьшее число пересечений. Эквивалентно, если граф может быть нарисован с меньшим числом пересечений, чем у K_n, тогда, согласно гипотезе, его можно раскрасить в меньше чем n цветов.

Гипотетическая формула минимального числа пересечений

Напрямую можно показать, что граф с ограниченным числом пересечений имеет ограниченное хроматическое число — можно назначить различные цвета концам всех пересекающихся рёбер и выкрасить в 4 цвета оставшийся после удаления этих рёбер планарный граф. Гипотеза Албертсона заменяет эту качественную связь между числом пересечений и числом цветов более точной количественной связью. Другая гипотеза Ричарда К. ГаяШаблон:Sfn утверждает, что число пересечений полного графа K_n равно

$\text{cr}(K_n)=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor .$

Известно, каким образом рисовать полные графы с таким числом пересечений, располагая вершины на двух концентрических окружностях. Что неизвестно, так это существуют ли рисунки с меньшим числом пресечений. Таким образом, усиленная формулировка гипотезы Албертсона гласит, что любой n-хроматический граф имеет число пересечений, не меньший правой части этой формулыШаблон:Sfn. Эта усиленная гипотеза справедлива тогда и только тогда, когда обе гипотезы, гипотеза Гая и гипотеза Албертсона, верны.

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

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

Специальные случаи

Гипотеза Албертсона является Шаблон:Не переведено 5 для $n⩽4$ — $K_4$ имеет число пересечений нуль и все графы имеют число пересечений, не меньшее нуля. Случай $n=5$ гипотезы Албертсона эквивалентен теореме о чётырёх красках, что любой планарный граф может быть раскрашен в четыре или меньше цветов, а единственные графы, для которых требуется меньше пересечений, чем у графа K₅, это планарные графы, по гипотезе же они должны быть не более чем 4-хроматическими. Благодаря поддержке некоторых групп авторов сейчас известно, что гипотеза верна для всех $n⩽16$Шаблон:SfnШаблон:SfnШаблон:Sfn. Для любого целого числа $c⩾6$ Луис и Рихтер представили семейства (c+1)-критических по цвету графов, которые не содержат подразделения полного графа K_(c+1), но имеющие число пересечений, не меньшее K_(c+1)Шаблон:Sfn.

Связанные гипотезы

Существует также связь с гипотезой Хадвигера, важной открытой проблеме комбинаторики, касающейся связи между хроматическим числом и существованием больших клик в качестве миноров графаШаблон:Sfn. Вариант гипотезы Хадвигера, выдвинутый Дьёрдьем Хайошем, утверждает, что любой n-хроматический граф содержит подразделение K_n. Если бы гипотеза была верна, из неё вытекала бы гипотеза Албертсона, поскольку число пересечений полного графа не меньше числа пересечений подразделения. Однако в настоящее время известны контрпримеры гипотезе ХайошаШаблон:SfnШаблон:Sfn, так что эта связь не даёт возможности доказательства гипотезы Албертсона.

Литература

• Шаблон:Книга
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Книга. Как процитировано в статье Албертсона, Крэнстона и ФоксаШаблон:Harv
• Шаблон:Статья
• Шаблон:Статья