Гипотеза Эрдеша – Дьярфа - Erdős–Gyárfás conjecture

Вопрос, Web Fundamentals.svg Нерешенная задача по математике :
Должен ли каждый кубический граф содержать простой цикл длины, равной степени двойки?
(больше нерешенных задач по математике)
График Маркстрёма
Маркстрём-Graph.svg
Кубический планарный граф Маркстрёма с 24 вершинами без 4- или 8-циклов, найденный в результате компьютерного поиска контрпримеров к гипотезе Эрдеша – Дьярфаша. Однако в нем есть циклы с 16 вершинами.
Вершины 24
Края 36
Радиус 5
Диаметр 6
Обхват 3
Автоморфизмы 3
Таблица графиков и параметров

В теории графов недоказанная гипотеза Эрдеша – Гьярфаса , сделанная в 1995 году плодовитым математиком Полом Эрдёшем и его сотрудником Андрашем Дьярфасом , утверждает, что каждый граф с минимальной степенью 3 содержит простой цикл , длина которого равна степени двойки . Эрдеш предложил приз в размере 100 долларов за доказательство гипотезы или 50 долларов за контрпример; это одна из многих гипотез Эрдеша .

Если гипотеза неверна, контрпример мог бы принять форму графа с минимальной степенью три, не имеющего циклов степени двойки. Из компьютерных поисков Гордона Ройла и Класа Маркстрёма известно, что любой контрпример должен иметь не менее 17 вершин, а любой кубический контрпример должен иметь не менее 30 вершин. Поиски Маркстрёма обнаружили четыре графа с 24 вершинами, в которых единственный цикл со степенью двойки имеет 16 вершин. Один из этих четырех графиков плоский ; однако теперь известно, что гипотеза Эрдеша – Гьярфаша верна для частного случая 3-связных плоских кубических графов ( Heckman & Krakovski 2013 )

Известны более слабые результаты, связывающие степень графа с неизбежными наборами длин цикла: существует множество длин S , причем | S | = О ( п 0,99 ), таким образом, что каждый граф со средними десять градусов или более содержит цикл с его длиной в S ( VERSTRAETE 2005 ), и каждый граф, средней степень является экспоненциальным в повторном логарифме в п обязательно содержит цикл, длина которого представляет собой степень двойки ( Судаков и Верстраете, 2008 ). Известно также, что эта гипотеза верна для плоских графов без когтей ( Daniel & Shauger 2001 ) и для графов, которые избегают больших индуцированных звезд и удовлетворяют дополнительным ограничениям на их степени ( Shauger 1998 ).

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

  • Дэниел, Дейл; Шаугер, Стивен Э. (2001), "Результат о гипотезе Эрдеша – Дьярфа в плоских графах", Proc. 32-й Юго-Восточный международный Конф. Комбинаторика, теория графов и вычисления , стр. 129–139. .
  • Хекман, Кристофер Карл; Краковски, Рой (2013), "Гипотеза Эрдеша-Дьярфаса для кубических плоских графов" , Электронный журнал комбинаторики , 20 (2), P7 .
  • Маркстрём, Клас (2004), "Экстремальные графы для некоторых задач о циклах в графах" (PDF) , Congr. Numerantium , 171 : 179–192 .
  • Шаугер, Стивен Э. (1998), "Результаты по гипотезе Эрдеша – Дьярфа в K 1, m -свободных графах", Proc. 29-й Юго-восточный международный Конф. Комбинаторика, теория графов и вычисления , стр. 61–65.
  • Судаков, Бенни; Verstraëte, Жак (2008), «Длины цикла в разреженных графах», Combinatorica , 28 (3): 357–372, arXiv : 0707.2117 , doi : 10.1007 / s00493-008-2300-6 .
  • VERSTRAETE Жак (2005), "Неизбежные длины циклов в графах", Журнал теории графов , 49 (2): 151-167, DOI : 10.1002 / jgt.20072 .

внешние ссылки