The logarithmic gap in the Erdős–Gyárfás–Łuczak function $f_r(k)$: is $f_r(k)=\Theta_r(k^{r/(r-1)})$ for fixed $r\ge 3$?

The function $f_r(k)$ of Erdős, Gyárfás and Łuczak (1994) is the largest $n$ such that every $[n,k,r]$-hypergraph — an $r$-uniform hypergraph with $n$ vertex classes of size $k$ and exactly one edge spanning each $r$-tuple of classes — admits an independent transversal, i.e. an independent set meeting every class in one vertex. For fixed $r$ they proved $c_r k^{r/(r-1)}\le f_r(k)\le C_r k^{r/(r-1)}(\ln k)^{1/(r-1)}$, by the Lovász Local Lemma and a first-moment random construction respectively, and asked for the correct order. The graph case $r=2$, where $\frac{1}{2e}k^2\le f_2(k)\le(1+o(1))k^2$, was resolved in 2022: Glock and Sudakov, and independently Kang and Kelly, proved $f_2(k)=(1+o(1))k^2$. For $r\ge 3$, however, the logarithmic factor survives; Glock and Sudakov call its removal 'perhaps the most significant open problem for $r>2$' and conjecture $f_r(k)=\Theta_r(k^{r/(r-1)})$, while their general theorem covers only $s\ge(r-1)!$ edges per $r$-tuple of classes, excluding the original $s=1$ case.

Background

Independent transversals. Let the vertex set of a graph or hypergraph be partitioned into classes ('parts') $V_1,\dots,V_m$. An independent transversal is an independent set — one containing no edge — that meets every part in exactly one vertex. (A hypergraph is $r$-uniform if every edge has exactly $r$ vertices.) Existence criteria for independent transversals have been studied since the early 1970s in connection with colouring problems such as the strong chromatic number (a strengthening of ordinary graph colouring in which each colour class must also be spread across the parts) and list colouring; the classical tight results concern parts that are large relative to the maximum degree $\Delta$ (parts of size $2\Delta$ suffice and are best possible in general), and Loh and Sudakov (2007) proved an influential criterion under a local-sparsity hypothesis.

The Erdős–Gyárfás–Łuczak model. Erdős, Gyárfás and Łuczak (1994) introduced an extremal question in the opposite, very sparse regime. An $[n,k,r]$-hypergraph is an $r$-uniform hypergraph whose vertex set is partitioned into $n$ classes $V_1,\dots,V_n$ of size $k$ each, such that every edge meets exactly $r$ of the classes in one vertex each, and for every choice of $r$ classes there is exactly one edge meeting precisely those classes and no others. Thus the hypergraph has exactly $\binom{n}{r}$ edges — one per $r$-tuple of classes — and for $r=2$ it is a graph in which every pair of classes is joined by exactly one edge. Let $f_r(k)$ be the largest $n$ such that every $[n,k,r]$-hypergraph has an independent transversal. The purpose of the 1994 note was to estimate $f_r(k)$.

The two bounds. Throughout, asymptotics are as $k\to\infty$ with $r$ fixed, and $O_r,\Omega_r,\Theta_r$ suppress constants depending only on $r$. Two standard probabilistic tools bracket $f_r(k)$. The Lovász Local Lemma (which implies that individually unlikely, weakly dependent 'bad' events are simultaneously avoided with positive probability) gives, for a suitable constant $c_r>0$,

$$f_r(k)\;\ge\;c_r\,k^{r/(r-1)},$$

because a uniformly random transversal then avoids all edges with positive probability. Conversely, a first-moment (expectation) argument shows that a random $[n,k,r]$-hypergraph has no independent transversal with positive probability once $n$ exceeds the threshold, giving, for some $C_r>0$,

$$f_r(k)\;\le\;C_r\,k^{r/(r-1)}(\ln k)^{1/(r-1)}.$$

These differ by the factor $(\ln k)^{1/(r-1)}$ — the logarithmic gap. For $r=2$ the corresponding statement is $\frac{1}{2e}k^2\le f_2(k)\le(1+o(1))k^2$, where the upper bound comes not from the random construction but from an explicit algebraic construction built on an affine plane (the point–line incidence structure of a 2-dimensional vector space over a finite field) of order $k+1$: Erdős, Gyárfás and Łuczak conjectured that this upper bound is tight, i.e. that $f_2(k)=(1+o(1))k^2$.

The 2022 resolution of the graph case. Glock and Sudakov (2022) proved a general theorem guaranteeing an independent transversal under an average-degree condition in locally sparse partite graphs, and deduced $f_2(k)=(1+o(1))k^2$, proving the 1994 conjecture; Kang and Kelly (2022) independently proved a semi-random (nibble-type, iterated random embedding) criterion with the same consequence. In the notation of Glock–Sudakov, an $(n,k,r,s)$-graph allows $s$ edges (forming a matching) between each $r$-tuple of classes, and $f(k,r,s)$ is the corresponding extremal function, so the original function is $f_r(k)=f(k,r,1)$. They also settled a 1997 conjecture of Yuster by proving $f(k,2,s)=(1+o_k(1))k^2/s$ for $1\le s\le k$, and proved $f(k,r,s)=\Theta_r((k^r/s)^{1/(r-1)})$ whenever $(r-1)!\le s\le k$ — that is, the logarithmic factor is removable once $s$ is at least $(r-1)!$.

What remains open. For $s=1$ and $r\ge 3$ — the original function $f_r(k)$ — nothing beyond the 1994 bounds is known. Glock and Sudakov state that 'perhaps the most significant open problem for $r>2$ is to get rid of the extra log-factor', adding that they 'cannot prove that $f(k,r,1)=O_r(k^{r/(r-1)})$', and they conjecture $f(k,r,s)=\Theta_r((k^r/s)^{1/(r-1)})$ for all $s$. Their method pinpoints the obstruction: by a reduction (their Lemma 1.7) to a minimum-degree version $w(n,m;r,s)$ of the Zarankiewicz function (an extremal function for bipartite graphs with restricted common-neighbour counts, closely tied to the Turán problem — the maximum number of edges in a graph avoiding a fixed subgraph — for complete bipartite graphs $K_{r,s}$), the required constructions for $r\ge 3$ would follow from Turán-type estimates that are notoriously open. Wanless and Wood (2022) improved the constant in the Local-Lemma lower bound when $k$ is large relative to $r$, but the logarithmic gap for fixed $r\ge 3$ is untouched by all known methods.

Problem Statement

Determine the order of magnitude of $f_r(k)$ as $k\to\infty$ for each fixed integer $r\ge 3$, where $f_r(k)$ is the largest $n$ such that every $[n,k,r]$-hypergraph — an $r$-uniform hypergraph on $n$ vertex classes of size $k$ in which every edge meets $r$ distinct classes in one vertex each and each $r$-tuple of classes spans exactly one edge — admits an independent transversal (an independent set meeting every class in exactly one vertex). The known bounds are

$$c_r\,k^{r/(r-1)}\;\le\;f_r(k)\;\le\;C_r\,k^{r/(r-1)}(\ln k)^{1/(r-1)}$$

with $c_r,C_r>0$ depending only on $r$ (lower bound: Lovász Local Lemma; upper bound: first-moment random construction). The order of magnitude of $f_r(k)$ lies within the currently known bracket, whose two extremes are:

(a) The logarithmic factor is removable (the conjecture of Glock–Sudakov): $f_r(k)=O_r(k^{r/(r-1)})$, hence $f_r(k)=\Theta_r(k^{r/(r-1)})$. Settling this requires constructing $[n,k,r]$-hypergraphs with no independent transversal at $n\ge c\,k^{r/(r-1)}$ — a hypergraph analogue of the affine-plane construction that settles $r=2$, beating the first-moment random bound — or proving such hypergraphs exist indirectly.

(b) The logarithmic factor is intrinsic: $f_r(k)=\Omega_r(k^{r/(r-1)}(\ln k)^{1/(r-1)})$, i.e. every $[n,k,r]$-hypergraph with $n\le c_r\,k^{r/(r-1)}(\ln k)^{1/(r-1)}$ has an independent transversal, so the first-moment threshold is essentially the truth.

The question concerns every fixed $r\ge 3$, and no single value of $r\ge 3$ is currently settled. Once the order of magnitude is settled, a natural further question — not part of the present target — is the leading constant, currently unknown for every $r\ge 3$: as Glock–Sudakov observe, neither generic bound gives the correct constant even for $r=2$, where it is $1$.

References

1. Paul Erdős, András Gyárfás, Tomasz Łuczak. Independent Transversals in Sparse Partite Hypergraphs. Combinatorics, Probability and Computing 3(3) (1994) 293–296. DOI: 10.1017/S0963548300001206, https://doi.org/10.1017/S0963548300001206.
2. Raphael Yuster. Independent Transversals and Independent Coverings in Sparse Partite Graphs. Combinatorics, Probability and Computing 6(1) (1997) 115–125. DOI: 10.1017/S0963548396002763, https://doi.org/10.1017/S0963548396002763.
3. Po-Shen Loh, Benny Sudakov. Independent transversals in locally sparse graphs. Journal of Combinatorial Theory, Series B 97(6) (2007) 904–918. DOI: 10.1016/j.jctb.2007.02.003, https://doi.org/10.1016/j.jctb.2007.02.003.
4. Kyle MacKeigan. Independent coverings and orthogonal colourings. Discrete Mathematics 344(8) (2021) 112431. DOI: 10.1016/j.disc.2021.112431, arXiv:2008.07904, https://arxiv.org/abs/2008.07904.
5. Raphael Yuster. On Factors of Independent Transversals in k-Partite Graphs. The Electronic Journal of Combinatorics 28(4) (2021). DOI: 10.37236/10529, arXiv:2103.09139, https://arxiv.org/abs/2103.09139.
6. Stefan Glock, Benny Sudakov. An average degree condition for independent transversals. Journal of Combinatorial Theory, Series B 154 (2022) 370–391. DOI: 10.1016/j.jctb.2022.01.004, arXiv:2003.01683, https://arxiv.org/abs/2003.01683.
7. Ross J. Kang, Tom Kelly. Colorings, transversals, and local sparsity. Random Structures & Algorithms 61(1) (2022) 173–192. DOI: 10.1002/rsa.21051, arXiv:2003.05233, https://arxiv.org/abs/2003.05233. (The arXiv preprint carries the British-spelled title 'Colourings, transversals and local sparsity'; the citation uses the published journal title, to which the DOI resolves.)
8. Ian M. Wanless, David R. Wood. A General Framework for Hypergraph Coloring. SIAM Journal on Discrete Mathematics 36(3) (2022) 1663–1677. DOI: 10.1137/21M1421015, arXiv:2008.00775, https://arxiv.org/abs/2008.00775. (The arXiv preprint carries the British-spelled title 'A general framework for hypergraph colouring'; the citation uses the published journal title, to which the DOI resolves.)
9. Penny Haxell, Ronen Wdowinski. Constructing Graphs with No Independent Transversals. The Electronic Journal of Combinatorics 31(2) (2024). DOI: 10.37236/12429, https://doi.org/10.37236/12429.
10. Debsoumya Chakraborti, Tuan Tran. Approximate packing of independent transversals in locally sparse graphs. Journal of Combinatorial Theory, Series B 175 (2025) 187–212. DOI: 10.1016/j.jctb.2025.07.005, https://doi.org/10.1016/j.jctb.2025.07.005.