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

Задача по теории графов

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

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

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

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

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

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

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

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

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

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

Графики Кэли

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

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

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

Направленный граф Кэли

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

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

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

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

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

• ${\displaystyle a=(1,2,\dots ,n),b=(1,2)}$(длинный цикл и транспозиция ).
• ${\displaystyle s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)}$( Генератор Кокстера ). В этом случае гамильтонов цикл генерируется алгоритмом Штейнхауза–Джонсона–Троттера .
• любой набор транспозиций, соответствующий помеченному дереву на . ${\displaystyle \{1,2,..,n\}}$
• ${\displaystyle 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]

Общие группы

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

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

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

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

Ссылки

1. Бабай, Ласло (1996), «Группы автоморфизмов, изоморфизм, реконструкция», Справочник по комбинаторике , т. 2, Elsevier, стр. 1447–1540, ISBN 9780262571715, архивировано из оригинала 2007-06-13
2. Кнут, Дональд Э. (2014), "§7.2.1.2 Генерация всех перестановок", Комбинаторные алгоритмы, часть 1, Искусство программирования , т. 4A, Addison-Wesley, ISBN 978-0-13-348885-2
3. Ройл, Гордон, Cubic Symmetric Graphs (The Foster Census), архивировано из оригинала 20 июля 2008 г.
4. Хольштынский, В.; Штрубе, RFE (1978), «Пути и контуры в конечных группах», Дискретная математика , 22 (3): 263–272, doi : 10.1016/0012-365X(78)90059-6 , MR  0522721.
5. Стонг, Ричард (1987), «О гамильтоновых циклах в графах Кэли сплетений», Дискретная математика , 65 (1): 75–80, doi : 10.1016/0012-365X(87)90212-3 , MR  0891546
6. Пак, Игорь ; Радойчич, Радош (2009), «Гамильтоновы пути в графах Кэли» (PDF) , Дискретная математика , 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), «Разреженные псевдослучайные графы являются гамильтоновыми», Журнал теории графов , 42 : 17–33, CiteSeerX 10.1.1.24.553 , doi : 10.1002/jgt.10065, S2CID  2849709