Transversal Hajnal–Szemerédi conjecture

Let k2k\geq 2 be an integer, and let nn be a sufficiently large multiple of kk. Let

G=(G1,G2,,Gnk(k2))\bm{G}=\left(G_1,G_2,\ldots,G_{\frac{n}{k}\binom{k}{2}}\right)

be a collection of graphs on a common vertex set of size nn. Write δ(G)\delta(\bm{G}) for the minimum degree over all graphs in the collection, and let a transversal copy of a KkK_k-factor mean a collection of vertex-disjoint copies of KkK_k covering all vertices, using exactly one edge from each graph in G\bm{G}. Transversal Hajnal–Szemerédi conjecture. If

δ(G)(11k)n,\delta(\bm{G})\geq\left(1-\frac{1}{k}\right)n,

then G\bm{G} contains a transversal copy of a KkK_k-factor.

This is presented as a transversal analogue of the Hajnal–Szemerédi theorem and would generalise that theorem. The source gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Yangyang Cheng and Katherine Staden, “Stability of transversal Hamilton cycles and paths”, arXiv:2403.09913 (2024).

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.