View source for Draft:Aharoni-Korman conjecture

{{Draft article}}
{{Short description|Disproved statement in combinatorics}}
{{orphan|date=December 2024}}
The '''Aharoni-Korman conjecture''', also known as the '''fish-bone conjecture''', was a proposed statement in [[combinatorics]] and [[graph theory]] concerning [[Matching (graph theory)|matchings]] in [[Bipartite graph|bipartite graphs]] under degree constraints. 

== Description ==
{{unreferenced section|date= December 2024}}
Initially conjectured by [[Ron Aharoni]] and his student Vladimir Korman, the conjecture was widely believed to be true, with many attempting to prove its correctness since its inception. However, in November 2024, the conjecture was disproven by Lawrence Hollom, a [[mathematician]] and [[Large numbers|googologist]] at the [[University of Cambridge]], who provided a [[counterexample]] that demonstrated its failure under certain conditions.

== Formulation ==
A subset <math>X</math> of a partially ordered set, or poset, <math>P</math>, is a ''[[Chain (mathematics)|chain]]'' if the elements of <math>X</math> are [[Pairwise comparison|pairwise comparable]], and it is an ''[[antichain]]'' if its elements are pairwise incomparable. If <math>P</math> has no infinite antichain, then we say that it satisfies the ''finite antichain condition''.

In 1992, Aharoni and Korman posed the following conjecture:

If a poset <math>P</math> contains no infinite antichain then, for every positive integer <math>k</math>, there exist <math>k</math> chains <math>C_1, C_2, \dots, C_k</math> and a partition of <math>P</math> into disjoint antichains <math>(A_i  : i \in I)</math> such that each <math>A_i</math> meets <math>\min(\left| A_i \right|, k)</math> chains <math>C_j</math>.

For example, if <math>P</math> is the poset on the set <math>\mathbb{N} \times \mathbb{N}</math> with ordering given by setting <math>(x,y) \le (u,v)</math> if and only if <math>x \le u</math> and <math>y \le v</math>, then the <math>k=1</math> case of the conjecture holds by taking <math>C=\{(0,y):y\in \mathbb{N}\} \text{ and } A_i =\{(x,y) \in P: x+y=i\}</math> for all integers <math>i \ge 0</math>.

== Disproof ==
Lawrence Hollom disproved this conjecture in his paper titled "A Resolution of the Aharoni-Korman Conjecture".<ref>{{Cite web |title=Search {{!}} arXiv e-print repository |url=https://arxiv.org/search/math?query=a+resolution+of+the+aharoni-korman+conjecture&searchtype=all&abstracts=show&order=-announced_date_first&size=50 |access-date=2024-12-13 |website=arxiv.org |language=en}}</ref> Its disproof was also discussed in great length on Trefor Bazett's [[YouTube]] channel.<ref>{{Cite AV media |url=https://www.youtube.com/watch?si=yrn8swmqUbAbNzFV&v=YQnEB5rio_A&feature=youtu.be |title=Math News: The Fish Bone Conjecture has been deboned!! |date=2024-12-11 |last=Dr. Trefor Bazett |access-date=2024-12-13 |via=YouTube}}</ref>

== References ==
{{Reflist}}

{{Draft categories|
[[Category:Disproved conjectures]]
[[Category:Combinatorics]]
}}

{{Drafts moved from mainspace|date=December 2024}}