← All problems

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