2025/08/28 by Delcourt, Michelle, Henderson, Cicely, Lesgourgues, Thomas +1 · 4 citations
#05B05 #05B07 #05B15 #05B40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.20819
A central open question in extremal design theory is Nash-Williams' Conjecture from 1970 that every K3-divisible graph on n vertices (for n large enough) with minimum degree at least 3n/4 has a K3-decomposition. A folklore generalization of Nash-Williams' Conjecture extends this to all q≥ 4 by positing that every Kq-divisible graph on n vertices (for n large enough) with minimum degree at least (1-(1)/(q+1))n has a Kq-decomposition. We disprove this conjecture for all q≥ 4; namely, we show that for each q≥ 4, there exists c > 1 such that there exist infinitely many Kq-divisible graphs G with minimum degree at least (1-(1)/(c⋅(q+1)))v(G) and no Kq-decomposition; indeed we construct them admitting no fractional Kq-decomposition thus disproving the fractional relaxation of this conjecture. Our result also disproves the more general partite version. Indeed, we even show the folklore conjecture is off by a multiplicative factor by showing that for every ε > 0 and every large enough integer q, there exist infinitely many Kq-divisible graphs G with minimum degree at least (1-(1)/(((1+√(2))/(2)-ε)⋅ (q+1)))v(G) with no (fractional) Kq-decomposition.