Draft:Aharoni-Korman conjecture

Template:Draft article Template:Short description Template:Orphan The Aharoni-Korman conjecture, also known as the fish-bone conjecture, was a proposed statement in combinatorics and graph theory concerning matchings in bipartite graphs under degree constraints.

Description

Template:Unreferenced section 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 googologist at the University of Cambridge, who provided a counterexample that demonstrated its failure under certain conditions.

Formulation

A subset $X$ of a partially ordered set, or poset, $P$, is a chain if the elements of $X$ are pairwise comparable, and it is an antichain if its elements are pairwise incomparable. If $P$ 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 $P$ contains no infinite antichain then, for every positive integer $k$, there exist $k$ chains $C_1,C_2,\dots ,C_k$ and a partition of $P$ into disjoint antichains $(A_i:i\in I)$ such that each $A_i$ meets $\min (\left|A_i\right|,k)$ chains $C_j$.

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

Disproof

Lawrence Hollom disproved this conjecture in his paper titled "A Resolution of the Aharoni-Korman Conjecture". Its disproof was also discussed in great length on Trefor Bazett's YouTube channel.