WikiDer > Гипотеза Ловаса - Википедия

Lovász conjecture - Wikipedia

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

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

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

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

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

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

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

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

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

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

Графики Кэли

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

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

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

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

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

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

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

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

Когда группа это симметричная группа, есть много привлекательных генераторных установок. Например, гипотеза Ловаса верна в следующих случаях порождающих множеств:

Стонг показал, что гипотеза верна для графа Кэли венок Zм писатьZп с естественным минимальным порождающим множеством, когда м либо четное, либо три. В частности, это верно для кубические циклы, который может быть сгенерирован как граф Кэли сплетения Z2 писатьZп.[5]

Общие группы

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

  • (Ранкин генераторы)
  • (Рапапорт-Штрассер генераторы)
  • (ПакРадойчич генераторы[6])
  • куда (здесь имеем (2, s, 3) -презентация, Теорема Гловера – Марушича[7]).

Наконец, известно, что для любой конечной группы существует генераторный набор размером не более такой, что соответствующий граф Кэли является гамильтоновым (Пак-Радойчич). Этот результат основан на классификация конечных простых групп.

Гипотеза Ловаса была также установлена ​​для случайных порождающих множеств размера .[8]

Рекомендации

  1. ^ Ласло Бабай, Группы автоморфизмов, изоморфизм, реконструкция В архиве 2007-06-13 на Wayback Machine, в Справочник по комбинаторике, Vol. 2, Elsevier, 1996, 1447-1540.
  2. ^ Дональд Э. Кнут, Искусство программирования, Vol. 4, проект раздела 7.2.1.2.
  3. ^ Ройл, Гордон «Кубические симметричные графы (перепись Фостера)». В архиве 2008-07-20 на Wayback Machine
  4. ^ Holsztyński, W .; Strube, R. F. E. (1978), "Пути и схемы в конечных группах", Дискретная математика, 22 (3): 263–272, Дои:10.1016 / 0012-365X (78) 90059-6, МИСТЕР 0522721.
  5. ^ Стонг, Ричард (1987), "О гамильтоновых циклах в графах Кэли сплетений", Дискретная математика, 65 (1): 75–80, Дои:10.1016 / 0012-365X (87) 90212-3, МИСТЕР 0891546.
  6. ^ Игорь Пак, Радош Радойчич, Гамильтоновы пути в графах Кэли, 2002.
  7. ^ Гловер, Генри H .; Марушич, Драган (2007), "Гамильтоничность кубических графов Кэли", Журнал Европейского математического общества , 9 (4): 775–787, arXiv:математика / 0508647, Дои:10.4171 / JEMS / 96, МИСТЕР 2341831
  8. ^ Кривелевич Михаил; Судаков, Бенни (2003). «Редкие псевдослучайные графы гамильтоновы». Журнал теории графов. 42: 17–33. CiteSeerX 10.1.1.24.553. Дои:10.1002 / jgt.10065.