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 K_3 -divisible graph on n n vertices (for n n large enough) with minimum degree at least 3 n / 4 3n/4 has a K 3 K_3 -decomposition. A folklore generalization of Nash-Williams’ conjecture extends this to all q ≥ 4 q\ge 4 by positing that every K q K_q -divisible graph on n n vertices (for n n large enough) with minimum degree at least ( 1 − 1 q + 1 ) n \left (1-\frac {1}{q+1}\right )n has a K q K_q -decomposition. We disprove this conjecture for all q ≥ 4 q\ge 4 . Namely, we show that for each q ≥ 4 q\ge 4 , there exists c > 1 c > 1 such that there exist infinitely many
Fields of Study & Subjects
Computability
Logic
AI Algorithms
programming
and type systems
semigroups and automata theory
Publication details
- Journal / source
- Proceedings of the American Mathematical Society
- Volume
- 154
- Issue
- 10
- Pages
- 4107–4125
- Publication date
- 20 May 2026
- Language
- EN