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

Abstract

A central open question in extremal design theory is Nash-Williams' Conjecture from 1970 that every $K_3$-divisible graph on $n$ vertices (for $n$ large enough) with minimum degree at least $3n/4$ has a $K_3$-decomposition. A folklore generalization of Nash-Williams' Conjecture extends this to all $q\ge 4$ by positing that every $K_q$-divisible graph on $n$ vertices (for $n$ large enough) with minimum degree at least $\left(1-\frac{1}{q+1}\right)n$ has a $K_q$-decomposition. We disprove this conjecture for all $q\ge 4$; namely, we show that for each $q\ge 4$, there exists $c>1$ such that there exist infinitely many $K_q$-divisible graphs $G$ with minimum degree at least $\left(1-\frac{1}{c\cdot (q+1)}\right)v(G)$ and no $K_q$-decomposition; indeed we construct them admitting no fractional $K_q$-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 $\epsilon >0$ and every large enough integer $q$, there exist infinitely many $K_q$-divisible graphs $G$ with minimum degree at least $(1-\frac{1}{\left(\frac{1+\sqrt{2}}{2}-\epsilon \right)\cdot (q+1)})v(G)$ with no (fractional) $K_q$-decomposition.

15 pages, 3 figures, minor typos corrected, to appear in Proceedings of the AMS