← All problems

Nash-Williams' conjecture for triangle decompositions

14 years old · traced to

Let GG be a K3K_3-divisible graph, meaning that 33 divides e(G)e(G) and 22 divides dG(v)d_G(v) for every vertex vv, with nn vertices and minimum degree δ(G)\delta(G). A K3K_3-decomposition is a partition of the edges of GG into edge-disjoint triangles.

Nash-Williams' conjecture. If GG is K3K_3-divisible and

δ(G)≥34n,\delta(G) \geq \frac{3}{4}n,

then, for sufficiently large nn, GG admits a K3K_3-decomposition.

This is the central extremal conjecture in design theory. The paper presents a proof of the associated fractional conjecture, while the integral statement remains the target motivating the work.

References

13 papers in this index state this conjecture (2012–2026). The statement above is taken from the most recent of them; the others are arXiv:2512.04071, arXiv:2508.20819, arXiv:2008.00926, arXiv:1908.11076, arXiv:1808.06956, arXiv:1711.03382, arXiv:1507.04985, arXiv:1503.08191, arXiv:1402.2739, arXiv:1306.0342, arXiv:1212.4667, arXiv:1205.1558.

Source: Michelle Delcourt and Luke Postle, “A Proof of Nash-Williams' Conjecture”, arXiv:2606.11178 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.