The partite folklore clique decomposition conjecture

Let (V1,,Vq)(V_1,\ldots,V_q) be a balanced qq-partition of a qq-partite graph GG, with Vi=n|V_i|=n for every ii. Define

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

Call GG partite-KqK_q-divisible when, for every 1j1<j2q1\leq j_1<j_2\leq q and 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}).

Partite folklore conjecture. For each integer q4q\geq 4, the following holds for sufficiently large nn: if GG is a balanced partite-KqK_q-divisible qq-partite graph on qnqn vertices with

δ^(G)(11q+1)n,\hat{\delta}(G)\geq \left(1-\frac{1}{q+1}\right)n,

then GG admits a KqK_q-decomposition.

This is the partite counterpart of the folklore high-minimum-degree conjecture for KqK_q-decompositions and is connected to the existence of mutually orthogonal Latin squares. The source presents it as open.

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).

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.