Aharoni-Korman conjecture

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

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{\mathbb{N}}\times \mathbb{\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{\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.

References

This article "Aharoni-Korman conjecture" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Aharoni-Korman conjecture. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Nth K-Permutation
• Lattice ball
• Ideal ring bundle
• Combinatorial hierarchy

---