Давние догадки позже тривиально подтверждаются подтекстом

Я хотел бы знать, были ли предположения, которые давно не были доказаны в TCS, которые позже были подтверждены следствием другой теоремы, что, возможно, было легче доказать.

Эрдёш и Поса доказали, что для любого целого числа и любого графа либо имеет непересекающихся циклов, либо существует множество размерностей не более вершин такое что является лесом. (в их доказательстве ).$k$$G$$G$$k$$f(k)$$S\in G$$G\setminus S$$f(k) \in O(k \cdot \log k)$

Свойство Эрдеша и Поса фиксированного графа известное как следующее (не формальное определение):$H$

Класс графов допускает свойство Эрдеша-Поши, если существует функция такая, что для любого графа и для любого и для любого графа либо существует непересекающихся изоморфных копий (относительно минорных или подразделенных) группы в либо существует множество вершин , такое что и не имеет изоморфной копии .$\mathcal{C}$$f$$H\in \mathcal{C}$$k \in \mathbb{Z}$$G$$k$$H$$G$$S\in G$$|S|\le f(k)$$G\setminus S$$H$

После того, как результат Эрдёша и Поши для класса циклов, допускающих это свойство, оставался открытым вопрос, чтобы найти подходящий класс . В графе минор V доказано, что каждый планарный граф либо имеет ограниченную ширину дерева, либо содержит большую сетку как минор, имея в руках теорему о сетке, они показали, что свойство Эрдеша и Поса имеет место (для минора) тогда и только тогда, когда является классом плоских графов. Однако проблема все еще остается открытой для подразделения. Но доказательство теоремы относительно второстепенно несколько просто, и, насколько я знаю, нет доказательства без использования теоремы о сетке.$\mathcal{C}$$\mathcal{C}$

Недавние результаты для орграфов , дает ответы на давние открытые вопросы в аналогичной области для орграфов. например, один очень простой вопрос заключался в том, что существует ли функция такая, что для любого графа и целых чисел мы можем либо найти множество содержащее не более вершин, такое что не имеет цикл длины , по крайней мере или есть непересекающиеся циклы длины , по крайней мере в G . Это только частный случай, но для l = 2G k , l S ⊆ V ( G ) f ( k + l ) G - S l k $f$$G$$k,l$$S\subseteq V(G)$$f(k+l)$$G-S$$l$$k$$l$$G$$l=2$это было известно как гипотеза Младшего. До этого гипотеза Младшего была подтверждена Ридом и др. С довольно сложным подходом.

Стоит отметить, что до сих пор в орграфах есть несколько довольно нетривиальных случаев. например, теорема 5.6 в вышеприведенной статье является лишь положительным продолжением гипотезы младшего к небольшому классу слабо связанных орграфов, но с имеющимися у нас знаниями и математическими инструментами это не тривиально (или, может быть, мы не знаем простого аргумента для этого ). Возможно, предоставляя лучшую характеристику для этих графиков, будет более простой способ доказать это.

заголовок вопроса относится к «тривиальным последствиям», но его содержание точно не определяет этот критерий, так что это немного смешанное сообщение. один из самых известных предметов / примеров, который приближается к общей теме, является доказательством гипотезы о сильном совершенном графике (тогда ~ 4 десятилетия)в 2002 году Мария Чудновская, Нил Робертсон, Пол Сеймур и Робин Томас. проблема алгоритмической сложности распознавания совершенных графов оказалась тесно связана с механикой доказательства сильной гипотезы о совершенном графе, хотя до доказательства этой гипотезы это было не совсем хорошо понято или известно. другими словами, была неформальная гипотеза о том, что «идеальное распознавание графа в P» (или «низкая сложность» и т. д.) относительно быстро разрешается, основываясь на анализе / свойствах / механике теоремы о сильном идеальном графе.

Полиномиальный алгоритм распознавания совершенных графов Жерар Корнейольс, Синьмин Лю, Кристина Вушкович 2003