Badakhshian–Falgas-Ravry–Sharifzadeh traversal-density conjecture

Badakhshian, Falgas-Ravry, and Sharifzadeh formulated the conjecture in 2023: the density threshold for a Hamiltonian traversal of an $r$-partite graph should tend to $1/2$ as $r$ tends to infinity.

Known results

• Badakhshian, Falgas-Ravry, and Sharifzadeh (2023) proved the lower bound $\pi_r(C_r)>1/2$ for every $r\ge 3$.
• Lengler, Martinsson, Petrova, Schnider, Steiner, Weber, and Welzl (2024) proved the connected-transversal analogue asymptotically, giving limiting threshold $(3-\sqrt{5})/2$.

August 2026 claimed proof

A new preprint by Isabel McGuigan states that, for every $\varepsilon>0$ and all sufficiently large $r$, $\pi_r(C_r)<1/2+\varepsilon$, which together with the earlier lower bound proves the conjectured limit. It also gives asymptotic results for several factor classes, while identifying the $5$-cycle and Hamiltonian-path thresholds as remaining questions.

Current status (as of August 2026): The Hamiltonian-transversal limit is claimed in a new preprint but is not independently verified; the connected-transversal analogue is asymptotically proved, and related thresholds remain open.