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

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

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

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

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

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

{\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 .

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

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

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

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

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

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

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

Примечания

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

Ссылки

Акерман, Эял (2019), «О топологических графах с не более чем четырьмя пересечениями на ребро», Вычислительная геометрия , 85 : 101574, 31, arXiv : 1509.01932 , doi : 10.1016/j.comgeo.2019.101574 , MR 4010251 , S2CID 16 847443
Альбертсон, Майкл О.; Крэнстон, Дэниел В.; Fox, Jacob (2009), «Окрашивания, перекрестки и клики» (PDF) , Электронный журнал Combinatorics , 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), «Числа пересечений графов», в Алави, Ю .; Лик, ДР; Уайт, А.Т. (ред.), Теория графов и ее приложения: материалы конференции в Университете Западного Мичигана, Каламазу, Мичиган, 10–13 мая 1972 г. , Нью-Йорк: Springer-Verlag, стр. 111–124 . Цитируется Альбертсоном, Крэнстоном и Фоксом (2009) .
Опоровски, Б.; Чжао, Д. (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 .

[1] По данным Albertson, Cranston & Fox (2009) , гипотеза была высказана Альбертсоном на специальной сессии Американского математического общества в Чикаго, состоявшейся в октябре 2007 года.

[2] Хатчинсон, Джоан П. (19 июня 2009 г.), Памяти Майкла О. Альбертсона, 1946–2009: сборник его выдающихся гипотез и вопросов по теории графов (PDF) , Группа деятельности SIAM по дискретной математике .

[acf09-3] Перейти обратно: ^а ^б Альбертсон, Крэнстон и Фокс (2009) .

[4] Опоровски и Чжао (2009) ; Альбертсон, Крэнстон и Фокс (2009) ; Барат и Тот (2010) ; Акерман (2019) .

[5] Луис и Рихтер (2014) .

[6] Барат и Тот (2010) .

[7] Кэтлин (1979) ; Эрдеш и Файтлович (1981) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]