WikiDer > Гипотеза Кельмана – Сеймура

Kelmans–Seymour conjecture
K5 подразделение 12-вершины граф короны

В теория графов, то Гипотеза Кельмана – Сеймура заявляет, что каждый 5-вершинно-связный график, который не планарный содержит подразделение 5-вершины полный график K5. Он назван в честь Пол Сеймур и Александр Кельманс, который независимо описал гипотезу; Сеймур в 1977 году и Кельманс в 1979 году.[1][2] Доказательство было объявлено, но еще не опубликовано.[1][3]

Формулировка

Граф является 5-вершинно-связным, когда нет пяти вершин, удаление которых оставляет несвязный граф. Полный граф - это граф с ребром между каждыми пятью вершинами, и подразделение полного графа изменяет это, заменяя некоторые из его ребер более длинными путями. Итак, график г содержит подразделение K5 если можно выделить пять вершин г, и набор из десяти путей, соединяющих эти пять вершин попарно, при этом ни один из путей не имеет общих вершин или ребер друг с другом.

В любой рисование графика на евклидовой плоскости по крайней мере два из десяти путей должны пересекать друг друга, поэтому граф г который содержит K5 подразделение не может быть планарный граф. В другом направлении, по Теорема Куратовского, граф, который не является планарным, обязательно содержит подразделение K5 или из полный двудольный граф K3,3Гипотеза Кельмана – Сеймура уточняет эту теорему, обеспечивая условие, при котором только одно из этих двух подразделений, подразделение K5, можно гарантировать существование. В нем говорится, что если неплоский граф 5-вершинно-связный, то он содержит подразделение K5.

Связанные результаты

Связанный результат, Теорема Вагнера, утверждает, что каждый 4-вершинно-связный неплоский граф содержит копию K5 как граф минор. Один из способов переформулировать этот результат состоит в том, что на этих графиках всегда можно выполнить последовательность сжатие края операций так, чтобы результирующий граф содержал K5 подразделение. Гипотеза Кельмана – Сеймура утверждает, что при более высоком порядке связности эти сокращения не требуются.

Более ранняя гипотеза Габриэль Эндрю Дирак (1964), доказанный в 2001 году Вольфгангом Мадером, утверждает, что каждый п-вершинный граф не менее 3п − 5 ребра содержит подразделение K5. Поскольку планарные графы имеют не более 3п − 6 рёбер, графы не менее 3п − 5 ребра должны быть неплоскими. Однако они не обязательно должны быть 5-связными, и 5-связные графы могут иметь всего лишь 2.5п края.[4][5][6]

Заявленное доказательство

В 2016 году доказательство гипотезы Кельмана – Сеймура было заявлено Синсин Ю из Технологический институт Джорджии и его докторская степень. студенты Давэй Хэ и Ян Ван.[3]Серия из четырех статей, доказывающих эту гипотезу, появилась в Journal of Combinatorial Theory Series B.[7][8][9][10]

Смотрите также

использованная литература

  1. ^ а б Конди, Билл (30 мая 2016 г.), «Математическая загадка разгадана спустя 40 лет», Космос.
  2. ^ Однако обратите внимание, что Томассен (1997) датирует формулировку гипотезы Сеймуром 1984 годом.
  3. ^ а б Он, Давэй; Ван, Ян; Юй Синсин (16 ноября 2015 г.), Гипотеза Кельмана – Сеймура I: специальные разделения, arXiv:1511.05020; ——; и другие. (24 февраля 2016 г.), Гипотеза Кельмана – Сеймура II: 2-вершины в , arXiv:1602.07557; ——; и другие. (19 сентября 2016 г.), Гипотеза Кельмана – Сеймура III: 3-вершины в , arXiv:1609.05747; ——; и другие. (21 декабря 2016 г.), Гипотеза Кельмана – Сеймура IV: доказательство, arXiv:1612.07189
  4. ^ Дирак, Г.А. (1964), «Теоремы о гомоморфизме графов», Mathematische Annalen, 153: 69–80, Дои:10.1007 / BF01361708, Г-Н 0160203
  5. ^ Томассен, Карстен (1997), "Гипотеза Дирака о -подразделения », Дискретная математика, 165/166: 607–608, Дои:10.1016 / S0012-365X (96) 00206-3, Г-Н 1439305
  6. ^ Мадер, В. (1998) " края действительно заставляют подразделение ", Комбинаторика, 18 (4): 569–595, Дои:10.1007 / s004930050041, Г-Н 1722261
  7. ^ Он, Давэй; Ван, Ян; Юй Синсин (11.12.2019). "Гипотеза Кельмана-Сеймура I: Особые разделения". Журнал комбинаторной теории, серия B. arXiv:1511.05020. Дои:10.1016 / j.jctb.2019.11.008. ISSN 0095-8956.
  8. ^ Он, Давэй; Ван, Ян; Юй Синсин (11.12.2019). "Гипотеза Кельмана-Сеймура II: 2-вершины в K4−". Журнал комбинаторной теории, серия B. arXiv:1602.07557. Дои:10.1016 / j.jctb.2019.11.007. ISSN 0095-8956.
  9. ^ Он, Давэй; Ван, Ян; Юй Синсин (2019-12-09). "Гипотеза Кельмана-Сеймура III: 3-вершины в K4−". Журнал комбинаторной теории, серия B. arXiv:1609.05747. Дои:10.1016 / j.jctb.2019.11.006. ISSN 0095-8956.
  10. ^ Он, Давэй; Ван, Ян; Юй Синсин (19.12.2019). "Гипотеза Кельмана-Сеймура IV: Доказательство". Журнал комбинаторной теории, серия B. arXiv:1612.07189. Дои:10.1016 / j.jctb.2019.12.002. ISSN 0095-8956.