Гипотеза Ловаса

В теории графов гипотеза Ловаса (1969) является классической проблемой о гамильтоновых путях в графах . Там говорится:

Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов путь.

Первоначально Ласло Ловаш сформулировал проблему противоположным образом, но эта версия стала стандартной. В 1996 году Ласло Бабай опубликовал гипотезу, резко противоречащую этой гипотезе: ^{[ 1 ]} но обе гипотезы остаются широко открытыми . Неизвестно даже, ли один-единственный контрпример приведет к серии контрпримеров.

Исторические замечания

Проблема поиска гамильтоновых путей в высокосимметричных графах довольно старая. Как описывает это Дональд Кнут в четвертом томе «Искусства компьютерного программирования» : ^{[ 2 ]} проблема возникла в британской кампанологии (звон звона). Такие гамильтоновы пути и циклы также тесно связаны с кодами Грея . В каждом случае конструкции явные.

Варианты гипотезы Ловаса

гамильтонов цикл

Другая версия гипотезы Ловаса утверждает, что

Каждый конечный связный вершинно-транзитивный граф содержит гамильтонов цикл, за исключением пяти известных контрпримеров.

Существует 5 известных примеров вершинно-транзитивных графов без гамильтоновых циклов (но с гамильтоновыми путями): полный граф $K_{2}$ , граф Петерсена , граф Коксетера и два графа, полученные на основе графов Петерсена и Коксетера путем замены каждой вершины треугольником. ^{[ 3 ]}

Графики Кэли

Ни один из пяти вершинно-транзитивных графов без гамильтоновых циклов не является графом Кэли . Это наблюдение приводит к более слабой версии гипотезы:

Каждый конечный связный граф Кэли содержит гамильтонов цикл .

Преимущество формулировки графа Кэли состоит в том, что такие графы соответствуют конечной группе. $G$ и генераторная установка $S$ . Таким образом, можно спросить, для чего $G$ и $S$ гипотеза верна, а не подвергает ее критике в полной общности.

Ориентированный граф Кэли

Для ориентированных графов Кэли (орграфов) гипотеза Ловаса неверна. Различные контрпримеры были получены Робертом Александром Рэнкином . Тем не менее, многие из приведенных ниже результатов справедливы и в этих ограничительных условиях.

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

Гамильтонов путь в пермутоэдре , граф Кэли симметрической группы с генераторами Кокстера

Каждый направленный граф Кэли абелевой группы имеет гамильтонов путь; однако каждая циклическая группа которой , порядок не является степенью простого числа, имеет ориентированный граф Кэли, не имеющий гамильтонова цикла. ^{[ 4 ]} В 1986 году Д. Витте доказал, что гипотеза Ловаса верна для графов Кэли p -групп . Он открыт даже для групп диэдра , хотя для специальных наборов образующих достигнут некоторый прогресс.

Для симметричной группы $S_{n}$ , есть много привлекательных генераторных установок. Например, гипотеза Ловаса верна в следующих случаях порождающих множеств:

$a=(1,2,\dots ,n),b=(1,2)$ (длинный цикл и транспозиция ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( генераторы Кокстера ). В этом случае гамильтонов цикл генерируется алгоритмом Штейнхауса–Джонсона–Троттера .
любой набор транспозиций, соответствующий помеченному дереву на $\{1,2,..,n\}$ .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$

Стонг показал, что гипотеза верна для графа Кэли сплетения Z m _wr Z n _с естественным минимальным порождающим набором, когда или три m четно . В частности, это справедливо для кубически-связных циклов , которые могут быть сгенерированы как граф Кэли сплетения Z ₂ wr Z _n . ^{[ 5 ]}

Общие группы

Для общих конечных групп известны лишь несколько результатов:

$S=\{a,b\},(ab)^{2}=1$ ( Рэнкина ) генераторы
$S=\{a,b,c\},a^{2}=b^{2}=c^{2}=[a,b]=1$ ( генераторы Рапапорта – Штрассера )
$S=\{a,b,c\},a^{2}=1,c=a^{-1}ba$ ( Пака – Радоичича Генератор ^{[ 6 ]})
$S=\{a,b\},a^{2}=b^{s}=(ab)^{3}=1,$ где $|G|,s=2~mod~4$ (здесь мы имеем (2,s,3) -представление , теорему Гловера–Марушича). ^{[ 7 ]}

Наконец, известно, что для любой конечной группы $G$ существует порождающий набор размером не более $\log _{2}|G|$ такой, что соответствующий граф Кэли является гамильтоновым (Пак-Радойчич). Этот результат основан на классификации конечных простых групп .

Гипотеза Ловаса была также доказана для случайных порождающих наборов размера $\Omega (\log ^{5}|G|)$ . ^{[ 8 ]}

Ссылки

^ Бабай, Ласло (1996), «Группы автоморфизмов, изоморфизм, реконструкция» , Справочник по комбинаторике , том. 2, Elsevier, стр. 1447–1540, ISBN. 9780262571715 , заархивировано из оригинала 13 июня 2007 г.
^ Кнут, Дональд Э. (2014), «§7.2.1.2 Генерация всех перестановок», Комбинаторные алгоритмы, Часть 1 , Искусство компьютерного программирования , том. 4А, Аддисон-Уэсли, ISBN 978-0-13-348885-2
^ Ройл, Гордон, Кубические симметричные графы (Перепись Фостера) , заархивировано из оригинала 20 июля 2008 г.
^ Холштыньский, В.; Штрубе, RFE (1978), «Пути и схемы в конечных группах», Discrete Mathematics , 22 (3): 263–272, doi : 10.1016/0012-365X(78)90059-6 , MR 0522721 .
^ Стонг, Ричард (1987), «О гамильтоновых циклах в графах Кэли сплетений», Discrete Mathematics , 65 (1): 75–80, doi : 10.1016/0012-365X(87)90212-3 , MR 0891546
^ Пак, Игорь ; Радоичич, Радош (2009), «Гамильтоновы пути в графах Кэли» (PDF) , Discrete Mathematics , 309 (17): 5501–5508, doi : 10.1016/j.disc.2009.02.018
^ Гловер, Генри Х.; Марушич, Драган (2007), «Гамильтонность кубических графов Кэли», Журнал Европейского математического общества , 9 (4): 775–787, arXiv : math/0508647 , doi : 10.4171/JEMS/96 , MR 2341831
^ Кривелевич Михаил ; Судаков, Бенни (2003), «Разреженные псевдослучайные графы являются гамильтоновыми», Journal of Graph Theory , 42 : 17–33, CiteSeerX 10.1.1.24.553 , doi : 10.1002/jgt.10065 , S2CID 2849709

[1] Бабай, Ласло (1996), «Группы автоморфизмов, изоморфизм, реконструкция» , Справочник по комбинаторике , том. 2, Elsevier, стр. 1447–1540, ISBN. 9780262571715 , заархивировано из оригинала 13 июня 2007 г.

[2] Кнут, Дональд Э. (2014), «§7.2.1.2 Генерация всех перестановок», Комбинаторные алгоритмы, Часть 1 , Искусство компьютерного программирования , том. 4А, Аддисон-Уэсли, ISBN 978-0-13-348885-2

[3] Ройл, Гордон, Кубические симметричные графы (Перепись Фостера) , заархивировано из оригинала 20 июля 2008 г.

[4] Холштыньский, В.; Штрубе, RFE (1978), «Пути и схемы в конечных группах», Discrete Mathematics , 22 (3): 263–272, doi : 10.1016/0012-365X(78)90059-6 , MR 0522721 .

[5] Стонг, Ричард (1987), «О гамильтоновых циклах в графах Кэли сплетений», Discrete Mathematics , 65 (1): 75–80, doi : 10.1016/0012-365X(87)90212-3 , MR 0891546

[6] Пак, Игорь ; Радоичич, Радош (2009), «Гамильтоновы пути в графах Кэли» (PDF) , Discrete Mathematics , 309 (17): 5501–5508, doi : 10.1016/j.disc.2009.02.018

[7] Гловер, Генри Х.; Марушич, Драган (2007), «Гамильтонность кубических графов Кэли», Журнал Европейского математического общества , 9 (4): 775–787, arXiv : math/0508647 , doi : 10.4171/JEMS/96 , MR 2341831

[8] Кривелевич Михаил ; Судаков, Бенни (2003), «Разреженные псевдослучайные графы являются гамильтоновыми», Journal of Graph Theory , 42 : 17–33, CiteSeerX 10.1.1.24.553 , doi : 10.1002/jgt.10065 , S2CID 2849709

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]