Русская Википедия:Гипотеза Албертсона
Шаблон:Unsolved Гипотеза Албертсона — это недоказанная связь между числом пересечением и хроматическим числом графа. Гипотеза носит имя Михаила О. Албертсона, профессора колледжа Смит, который сформулировал утверждение в качестве гипотезы в 2007[1]. Гипотеза является одной из многих гипотез в теории раскраски графовШаблон:Sfn. Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф Kn находится среди графов, имеющих наименьшее число пересечений. Эквивалентно, если граф может быть нарисован с меньшим числом пересечений, чем у Kn, тогда, согласно гипотезе, его можно раскрасить в меньше чем n цветов.
Гипотетическая формула минимального числа пересечений
Напрямую можно показать, что граф с ограниченным числом пересечений имеет ограниченное хроматическое число — можно назначить различные цвета концам всех пересекающихся рёбер и выкрасить в 4 цвета оставшийся после удаления этих рёбер планарный граф. Гипотеза Албертсона заменяет эту качественную связь между числом пересечений и числом цветов более точной количественной связью. Другая гипотеза Ричарда К. ГаяШаблон:Sfn утверждает, что число пересечений полного графа Kn равно
- <math>\textrm{cr}(K_n)=\frac14\left\lfloor\frac{n}{2}\right\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.</math>
Известно, каким образом рисовать полные графы с таким числом пересечений, располагая вершины на двух концентрических окружностях. Что неизвестно, так это существуют ли рисунки с меньшим числом пресечений. Таким образом, усиленная формулировка гипотезы Албертсона гласит, что любой n-хроматический граф имеет число пересечений, не меньший правой части этой формулыШаблон:Sfn. Эта усиленная гипотеза справедлива тогда и только тогда, когда обе гипотезы, гипотеза Гая и гипотеза Албертсона, верны.
Асимптотические границы
Более слабая форма гипотезы, доказанная М. ШеферомШаблон:Sfn, утверждает, что любой граф с хроматическим числом n имеет число пересечений Ω(n4), или, эквивалентно, что любой граф с числом пересечений k имеет хроматическое число O(k1/4). Алберсон, Крэтсон и ФоксШаблон:Sfn опубликовали доказательство этих границ путём комбинации факта, что любой минимальный n-хроматический граф имеет минимальную степень, не меньшую <math>n - 1</math> (в противном случае можно было бы раскрасить его в <math>(n - 1)</math> цветов после удаления вершины с малой степенью, раскраски оставшегося графа и использования доступного цвета для удалённой вершины, что противоречит минимальности графа) вместе с неравенством для числа пересечений, согласно которому любой граф <math>G = (V,E)</math> с <math>|E|/|V| \geqslant 4</math> имеет число пересечений <math>\Omega(|E|^3/|V|^2</math>). Используя те же доводы, они показывают, что контрпример гипотезе Албертсона с хроматическим числом n (если таковой существует) должен иметь менее 4 n вершин.
Специальные случаи
Гипотеза Албертсона является Шаблон:Не переведено 5 для <math>n \leqslant 4</math> — <math>K_4</math> имеет число пересечений нуль и все графы имеют число пересечений, не меньшее нуля. Случай <math>n = 5</math> гипотезы Албертсона эквивалентен теореме о чётырёх красках, что любой планарный граф может быть раскрашен в четыре или меньше цветов, а единственные графы, для которых требуется меньше пересечений, чем у графа K5, это планарные графы, по гипотезе же они должны быть не более чем 4-хроматическими. Благодаря поддержке некоторых групп авторов сейчас известно, что гипотеза верна для всех <math>n \leqslant 16</math>Шаблон:SfnШаблон:SfnШаблон:Sfn. Для любого целого числа <math>c \geqslant 6</math> Луис и Рихтер представили семейства (c+1)-критических по цвету графов, которые не содержат подразделения полного графа K(c+1), но имеющие число пересечений, не меньшее K(c+1)Шаблон:Sfn.
Связанные гипотезы
Существует также связь с гипотезой Хадвигера, важной открытой проблеме комбинаторики, касающейся связи между хроматическим числом и существованием больших клик в качестве миноров графаШаблон:Sfn. Вариант гипотезы Хадвигера, выдвинутый Дьёрдьем Хайошем, утверждает, что любой n-хроматический граф содержит подразделение Kn. Если бы гипотеза была верна, из неё вытекала бы гипотеза Албертсона, поскольку число пересечений полного графа не меньше числа пересечений подразделения. Однако в настоящее время известны контрпримеры гипотезе ХайошаШаблон:SfnШаблон:Sfn, так что эта связь не даёт возможности доказательства гипотезы Албертсона.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга. Как процитировано в статье Албертсона, Крэнстона и ФоксаШаблон:Harv
- Шаблон:Статья
- Шаблон:Статья
- ↑ Согласно Албертсону, Кранстону и ФоксуШаблон:Harv гипотеза была сделана Албертсоном на специальной сессии Американского математического общества в Чикаго, состоявшейся в октябре 2007.
