The partite Nash-Williams conjecture

From papers

Let (V1,V2,V3)(V_1,V_2,V_3) be a partition of the vertices of a tripartite graph GG, with V1=V2=V3=n|V_1|=|V_2|=|V_3|=n. Define

δ^(G):=min{d(v,Vj):1j3, vV(G)Vj}.\hat{\delta}(G):=\min\{d(v,V_j):1\leq j\leq 3,\ v\in V(G)\setminus V_j\}.

Call GG partite-K3K_3-divisible when, for every vV(G)(Vj1Vj2)v\in V(G)\setminus(V_{j_1}\cup V_{j_2}), one has d(v,Vj1)=d(v,Vj2)d(v,V_{j_1})=d(v,V_{j_2}) for all 1j1<j231\leq j_1<j_2\leq 3.

Partite Nash-Williams conjecture. For sufficiently large nn, if GG is a balanced partite-K3K_3-divisible 33-partite graph on 3n3n vertices with

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

then GG admits a K3K_3-decomposition.

This is the tripartite analogue of Nash-Williams' conjecture and is equivalent to a high-density completion statement for partial Latin squares. The source presents it as open and notes that only bounds for its fractional relaxation and conditional transfer results are known.

Progress summary

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

Sources & referencesView supporting material

Primary source

Michelle Delcourt, Cicely Henderson, Thomas Lesgourgues and Luke Postle, “Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles”, arXiv:2508.20819 (2026).

Solutions 0

No solutions have been posted yet.