The odd-partite independent-transversal blowup conjecture

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 r≥5r\ge 5 and every integer s≥2s\ge 2, there should exist constants C>0C>0 and n0∈Nn_0\in\mathbb{N} such that every graph G∈Gr(n)G\in\mathcal{G}_r(n) with n≥n0n\ge n_0 and

Δ(G)≤r−12r−4n−Cn1−1/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.

References

Primary source

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

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.