Misplaced Pages

Revision as of 10:10, 13 December 2024

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

For example, if ${\displaystyle P}$ is the poset on the set ${\displaystyle \mathbb {N} \times \mathbb {N} }$ with ordering given by setting ${\displaystyle (x,y)\leq (u,v)}$ if and only if ${\displaystyle x\leq u}$ and ${\displaystyle y\leq v}$, then the ${\displaystyle k=1}$ case of the conjecture holds by taking ${\displaystyle C=\{(0,y):y\in \mathbb {N} \}{\text{ and }}A_{i}=\{(x,y)\in P:x+y=i\}}$ for all integers ${\displaystyle i\geq 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.

1. "Search | arXiv e-print repository". arxiv.org. Retrieved 2024-12-13.
2. Dr. Trefor Bazett (2024-12-11). Math News: The Fish Bone Conjecture has been deboned!!. Retrieved 2024-12-13 – via YouTube.