Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles

A central open question in extremal design theory is Nash-Williams' Conjecture from 1970 that every K₃-divisible graph on n vertices (for n large enough) with minimum degree at least $3n/4$ has a K₃-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+√22-ε)· (q+1))v(G) with no (fractional) Kq-decomposition.