Гипотеза Кельмана – Сеймура - Kelmans–Seymour conjecture

K₅ подразделение 12-вершины граф короны

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

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

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

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

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

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

Более ранняя гипотеза Габриэль Эндрю Дирак (1964), доказанный в 2001 году Вольфгангом Мадером, утверждает, что каждый п-вершинный граф не менее 3п − 5 ребра содержит подразделение K₅. Поскольку планарные графы имеют не более 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-вершины в ${\displaystyle K_{4}^{-}}$, arXiv:1602.07557; ——; и другие. (19 сентября 2016 г.), Гипотеза Кельмана – Сеймура III: 3-вершины в ${\displaystyle K_{4}^{-}}$, arXiv:1609.05747; ——; и другие. (21 декабря 2016 г.), Гипотеза Кельмана – Сеймура IV: доказательство, arXiv:1612.07189
4. Дирак, Г.А. (1964), «Теоремы о гомоморфизме графов», Mathematische Annalen, 153: 69–80, Дои:10.1007 / BF01361708, Г-Н  0160203
5. Томассен, Карстен (1997), "Гипотеза Дирака о ${\displaystyle K_{5}}$-подразделения », Дискретная математика, 165/166: 607–608, Дои:10.1016 / S0012-365X (96) 00206-3, Г-Н  1439305
6. Мадер, В. (1998) "${\displaystyle 3n-5}$ края действительно заставляют подразделение ${\displaystyle K_{5}}$", Комбинаторика, 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.