The odd-partite independent-transversal blowup conjecture

From papers

Let Gr(n)\mathcal{G}_r(n) be the class of rr-partite graphs with parts of size nn. An independent transversal with exactly ss vertices in each part is denoted by IT(s)IT(s). Odd-partite blowup conjecture. For every odd integer r5r\ge 5 and every integer s2s\ge 2, there should exist constants C>0C>0 and n0Nn_0\in\mathbb{N} such that every graph GGr(n)G\in\mathcal{G}_r(n) with nn0n\ge n_0 and

Δ(G)r12r4nCn11/s\Delta(G)\le \frac{r-1}{2r-4}n-Cn^{1-1/s}

contains an IT(s)IT(s). This is proposed as an analogue of the corresponding result for r=3r=3; the paper presents it as an open direction, with tightness related to the Zarankiewicz number.

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

Yantao Tang and Yi Zhao, “Number of independent transversals in multipartite graphs”, arXiv:2504.03950 (2025).

Solutions 0

No solutions have been posted yet.