Гипотеза Кельманса – Сеймура
В теории графов гипотеза Келманса -Сеймура утверждает, что каждый связный с 5 вершинами граф, который не является плоским, содержит подразделение с 5 вершинами полного графа K 5 . Он назван в честь Пола Сеймура и Александра Кельманса, которые независимо описали эту гипотезу; Сеймур в 1977 году и Кельманс в 1979 году. [ 1 ] [ 2 ] Доказательство было объявлено в 2016 году и опубликовано в четырех статьях в 2020 году.
Формулировка
[ редактировать ]Граф называется 5-вершинно связным, если ни одна удаленная вершина не оставляет несвязный граф. Полный граф — это граф с ребром между всеми пятью вершинами, и подразделение полного графа изменяет это, заменяя некоторые из его ребер более длинными путями. Таким образом, граф G содержит подразделение K 5 , если можно выбрать пять вершин G , и набор из десяти путей, соединяющих эти пять вершин попарно, причем ни один из путей не имеет общих вершин или ребер друг с другом.
В любом рисунке графа на евклидовой плоскости хотя бы два пути из десяти должны пересекаться, поэтому граф G , содержащий подразделение К 5 , не может быть плоским графом . В другом направлении, по теореме Куратовского , граф, который не является плоским, обязательно содержит подразделение либо K 5 , либо полного двудольного графа K 3,3 . Гипотеза Келманса-Сеймура уточняет эту теорему, предоставляя условие, при котором может быть гарантировано существование только одного из этих двух подразделений, подразделения K 5 . Он утверждает, что если непланарный граф 5-связен, то он содержит подразделение K 5 .
Связанные результаты
[ редактировать ]Связанный с этим результат, теорема Вагнера , утверждает, что каждый 4-связный непланарный граф содержит копию K 5 в качестве минора графа . Один из способов переформулировать этот результат состоит в том, что в этих графах всегда возможно выполнить последовательность операций сжатия ребер чтобы результирующий граф содержал подразделение K5 так , . Гипотеза Келманса-Сеймура утверждает, что при более высоком порядке связности эти сокращения не требуются.
Более ранняя гипотеза Габриэля Эндрю Дирака (1964), доказанная в 2001 году Вольфгангом Мадером, утверждает, что каждый граф с n -вершинами по крайней мере с 3 n - 5 ребрами содержит подразделение K 5 . Поскольку планарные графы имеют не более 3 n − 6 ребер, графы с хотя бы 3 n − 5 ребрами должны быть непланарными. Однако они не обязательно должны быть 5-связными, а 5-связные графы могут иметь всего 2,5 n ребер. [ 3 ] [ 4 ] [ 5 ]
Заявленное доказательство
[ редактировать ]В 2016 году о доказательстве гипотезы Кельманса-Сеймура заявил Синсин Юй из Технологического института Джорджии и его доктор философии. Студенты Давэй Хэ и Ян Ван. [ 1 ] Последовательность из четырех статей, доказывающих эту гипотезу, появилась в Журнале комбинаторной теории, серия B. [ 6 ] [ 7 ] [ 8 ] [ 9 ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Конди, Билл (30 мая 2016 г.), «Математическая загадка раскрыта спустя 40 лет» , Cosmos .
- ^ Однако обратите внимание, что Томассен (1997) датирует формулировку гипотезы Сеймура 1984 годом.
- ^ Дирак, Джорджия (1964), «Теоремы о гомоморфизме графов», Mathematische Annalen , 153 : 69–80, doi : 10.1007/BF01361708 , MR 0160203 , S2CID 121213793
- ^ Томассен, Карстен (1997), "Гипотеза Дирака о -подразделения», Дискретная математика , 165/166: 607–608, doi : 10.1016/S0012-365X(96)00206-3 , MR 1439305
- ^ Мэдер, В. (1998), " края требуют разделения ", Combinatorica , 18 (4): 569–595, doi : 10.1007/s004930050041 , MR 1722261 , S2CID 7311121
- ^ Он, Давэй; Ван, Ян; Ю, Синсин (11 декабря 2019 г.). «Гипотеза Кельманса-Сеймура I: Особые разделения» . Журнал комбинаторной теории, серия B. 144 : 197–224. arXiv : 1511.05020 . дои : 10.1016/j.jctb.2019.11.008 . ISSN 0095-8956 . S2CID 29791394 .
- ^ Он, Давэй; Ван, Ян; Ю, Синсин (11 декабря 2019 г.). «Гипотеза Кельманса-Сеймура II: 2-вершины в K4-» . Журнал комбинаторной теории, серия B. 144 : 225–264. arXiv : 1602.07557 . дои : 10.1016/j.jctb.2019.11.007 . ISSN 0095-8956 . S2CID 220369443 .
- ^ Он, Давэй; Ван, Ян; Ю, Синсин (09 декабря 2019 г.). «Гипотеза Кельманса-Сеймура III: 3-вершины в K4−» . Журнал комбинаторной теории, серия B. 144 : 265–308. arXiv : 1609.05747 . дои : 10.1016/j.jctb.2019.11.006 . ISSN 0095-8956 . S2CID 119625722 .
- ^ Он, Давэй; Ван, Ян; Ю, Синсин (19 декабря 2019 г.). «Гипотеза Кельманса-Сеймура IV: доказательство» . Журнал комбинаторной теории, серия B. 144 : 309–358. arXiv : 1612.07189 . дои : 10.1016/j.jctb.2019.12.002 . ISSN 0095-8956 . S2CID 119175309 .
