← All problems

Katona’s conjecture on alternating Hamilton cycles

Let PP be a finite poset with at least two elements. If there is an ordering p1,…,p∣P∣p_1,\dots,p_{|P|} of the elements of PP such that consecutive elements are comparable and p1<p2>p3<p4>⋯p_1<p_2>p_3<p_4>\cdots, then, for every integer r≥2r\ge 2, the product poset P×BrP\times B_r admits an alternating Hamilton cycle; that is, its elements can be cyclically ordered as x1,…,x∣P∣2rx_1,\dots,x_{|P|2^r} so that xi<xi+1x_i<x_{i+1} for odd ii and xi>xi+1x_i>x_{i+1} for even ii, with indices taken modulo ∣P∣2r|P|2^r. Here BrB_r denotes the Boolean lattice on an rr-element set, and P×BrP\times B_r has the coordinatewise partial order.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to prove Katona’s conjecture by turning the relevant path condition into an alternating Hamilton cycle, but the claim has not been independently verified.

Katona’s conjecture concerns when an alternating Hamilton-path hypothesis forces an alternating Hamilton-cycle construction. The reported work also gives structural classifications for alternating Hamilton paths and cycles in divisor lattices.

October 13, 2026 claimed proof

Yuxian Dong and Jianxi Mao claim that a product construction proves the conjecture and yields the additional divisor-lattice classifications. The result is presented in an unrefereed preprint.

Current status (as of October 2026): Dong and Mao’s preprint claims the conjecture is solved, but the claim remains unverified; no independently assessed proof was found.

Sources

Solutions 0

No solutions have been posted yet.