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

Нерешенная проблема в математике:

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

Полный график

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

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

Асимптотические оценки

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

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

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

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

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

Примечания

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