Transversal Hajnal–Szemerédi conjecture

At least 1 year old · documented by

Let k≥2k\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)≥(1−1k)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.

References

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.