Гипотеза Ахарони-Кормана ⇐ Васина Википедия

[wiki_en]

Гипотеза Ахарони-Кормана, также известная как «гипотеза рыбьей кости», была предложенным утверждением в комбинаторике и теории графов, касающимся сопоставления (теории графов) | сопоставлений в двудольном графе. |двудольные графы с ограничениями по степени. Первоначально выдвинутая Роном Ахарони и его учеником Владимиром Корманом, эта гипотеза широко считалась верной, и многие пытались доказать ее правильность с момента ее создания. Однако в ноябре 2024 года гипотеза была опровергнута Лоуренсом Холломом, математиком и гогологом из Кембриджского университета, который предоставил контрпример, продемонстрировавший ее несостоятельность при определенных условиях.

=== Формулировка ===
Подмножество X частично упорядоченного набора или частично упорядоченного набора P является «цепочкой (математика)|цепочкой», если элементы X являются парными сравнениями|попарно сравнимыми, и это антицепь|'антицепь'', если ее элементы попарно несравнимы. Если P не имеет бесконечной антицепи, то мы говорим, что он удовлетворяет «условию конечной антицепи».

В 1992 году Ахарони и Корман выдвинули следующую гипотезу:

Например, если P является упорядоченным набором в множестве \mathbb{N} \times \mathbb{N} с порядком, заданным установкой (x,y) \le (u,v) тогда и только тогда, когда x \le u и y \le v, тогда k=1 случай гипотеза верна, если взять C=\{(0,y):y\in \mathbb{N}\} \text{ и } A_i =\{(x,y) \in P: x+y=i \} для всех целых чисел i \ge 0.

=== Опровержение ===
Лоуренс Холлом опроверг эту гипотезу в своей статье под названием «Разрешение гипотезы Ахарони-Кормана»

Подробнее: https://en.wikipedia.org/wiki/Aharoni-Korman_conjecture