The unresolved regime of the Erdős–Gyárfás function $f(n,p,q)$: superlinearity between the linear and quadratic thresholds, threshold constants, and geometric variants

Literature-status audit of the open questions left by Erdős and Gyárfás (Combinatorica, 1997) on $f(n,p,q)$, the minimum number of colors in an edge-coloring of the complete graph $K_n$ in which every $p$-clique spans at least $q$ colors. Much of the original problem list is now settled: $f(n,4,5) = (5/6)n + o(n)$; the polynomial threshold is exactly $q = p$, so $f(n,p,p-1) = n^{o(1)}$; $f(n,5,8) = (6/7)n + o(n)$; quadratic-threshold leading constants are known for $p \in \{6,8,10\}$ and, for even $p$, reduce to Brown–Erdős–Sós extremal limits; and the geometric conjecture that planar point sets in which every 4 points determine 5 distinct distances must determine $\gg n^2$ distances was disproved by Tao. The surviving open core is precise: (1) decide whether $f(n,5,9)$ is linear or superlinear — the smallest case beyond all current lower-bound techniques, with known bounds $(6/7)(n-1) \le f(n,5,9) \le O(n^{3/2}/(\log n)^{1/2})$; (2) whether linear growth occurs only at the linear threshold $q = \binom{p}{2} - p + 3$ (open for $p = 5$ and for $p \ge 9$); (3) whether $f(n,4,4) = \Theta(\sqrt{n})$; (4) leading constants at both thresholds for general $p$; and (5) whether the geometric quantity $f_2(n,4,5)$ is superlinear. As of September 2026 all of these are open.

Background

A $(p,q)$-coloring of the complete graph $K_n$ is an edge-coloring in which every set of $p$ vertices spans at least $q$ distinct colors, and $f(n,p,q)$ is the minimum number of colors in such a coloring — a generalized Ramsey number introduced by Erdős and Shelah in 1975. At $q = 2$ the condition forbids monochromatic $p$-cliques, so $f(n,p,2)$ is governed by multicolor Ramsey numbers; at the opposite endpoint $q = \binom{p}{2}$ every $p$-clique must be rainbow (all its edges differently colored), which forces all $\binom{n}{2}$ edges of $K_n$ to carry distinct colors, so $f(n,p,\binom{p}{2}) = \binom{n}{2} = \Theta(n^2)$. Erdős and Gyárfás (1997) began the systematic study. Using the Lovász Local Lemma — a probabilistic tool showing that if each of many 'bad' events has small probability and limited dependence on the others, then with positive probability none occurs — they proved the general upper bound $f(n,p,q) = O(n^{(p-2)/(\binom{p}{2}-q+1)})$ (which is $o(n)$ for every $q$ below, and $o(n^2)$ for every $q$ below, the two thresholds defined next), and identified the linear threshold $q_{\mathrm{lin}}(p) = \binom{p}{2} - p + 3$, the value of $q$ at which $f(n,p,q)$ first grows linearly ($f(n,p,q_{\mathrm{lin}}) = \Theta(n)$), and the quadratic threshold $q_{\mathrm{quad}}(p) = \binom{p}{2} - \lfloor p/2 \rfloor + 2$, at which $f(n,p,q_{\mathrm{quad}}) = \Theta(n^2)$. They also proved by induction $f(n,p,p) \ge n^{1/(p-2)} - 1$ (so $\sqrt{n} - 1 \le f(n,4,4) \le O(n^{2/3})$), connected the even-$p$ quadratic regime to the Brown–Erdős–Sós extremal problem on hypergraphs in which no small vertex set spans too many edges (formalized in part (4) below), and raised geometric analogues: $f_d(n,p,q)$ is the minimum number of distinct distances determined by an $n$-point set in $\mathbb{R}^d$ in which every $p$ points determine at least $q$ distinct distances. Throughout, monotonicity in $q$ is used: a $(p,q')$-coloring is automatically a $(p,q)$-coloring for $q \le q'$, so $f(n,p,q) \le f(n,p,q')$. The 1997 paper posed a list of open questions: the leading constant of $f(n,4,5)$; whether linearity occurs only at $q_{\mathrm{lin}}(p)$ (its Problem 2); the order of $f(n,4,4)$ and of $f(n,5,9)$, the latter reduced (its Problem 1) to a question on proper edge-colorings of complete graphs (edge-colorings whose color classes are matchings) whose color-class unions avoid 4-edge paths and 4-edge cycles; whether $f(n,p,p-1)$ must be polynomially large (its Problem 3); the even-$p$ quadratic-threshold constants; the hypergraph connections; and the geometric variant, notably whether $f_2(n,4,5)/n \to \infty$ or $f_2(n,4,5) = o(n^2)$. Much of this list is now settled; the five questions below are the surviving core.

Problem Statement

Determine the following surviving open cases of the Erdős–Gyárfás generalized Ramsey problem, where $f(n,p,q)$ is the minimum number of colors in an edge-coloring of the complete graph $K_n$ in which every $p$-clique spans at least $q$ colors, $q_{\mathrm{lin}}(p) = \binom{p}{2} - p + 3$, and $q_{\mathrm{quad}}(p) = \binom{p}{2} - \lfloor p/2 \rfloor + 2$. (1) Flagship: is $f(n,5,9)$ linear or superlinear in $n$? The known bounds are $f(n,5,9) \ge f(n,5,8) \ge (6/7)(n-1)$ (monotonicity in $q$ plus the result of Gomez-Leos–Heath–Parker–Schwieder–Zerbib on $f(n,5,8)$) and $f(n,5,9) \le O(n^{3/2}/(\log n)^{1/2})$ (Bennett–Delcourt–Li–Postle, improving the 1997 Local-Lemma bound $O(n^{3/2})$); no superlinear lower bound and no linear upper bound is known. Here $q_{\mathrm{lin}}(5) = 8$ and $q_{\mathrm{quad}}(5) = 10$, so $q = 9$ sits exactly one step below the quadratic threshold. For the upper-bound side, the 1997 paper (Problem 1) reduces this to a question about proper edge-colorings (edge-colorings whose color classes are matchings): in a $(5,9)$-coloring, any three edges of one color must span at least six vertices — three such edges on at most five vertices would leave the $K_5$ on those vertices with at most eight distinct colors among its ten edges — so every color class is a matching or has at most two edges, and every $(5,9)$-coloring can be refined to a proper one with at most twice as many colors. Moreover, a proper edge-coloring of $K_n$ ($n \ge 5$) is a $(5,9)$-coloring if and only if the union of any two color classes contains no 4-edge path and no 4-edge cycle: four edges carrying at most two colors and lying on at most five vertices force some five-vertex set to span at most eight colors, and conversely a properly colored $K_5$ spanning at most eight colors must contain two colors each appearing on two edges, and those four edges always include a 4-edge path or a 4-edge cycle. Thus, up to a constant factor in the number of colors, a linear upper bound for $f(n,5,9)$ is equivalent to a proper edge-coloring of $K_n$ with a linear number of colors in which the union of any two color classes avoids 4-edge paths and 4-edge cycles; no such coloring is known, and conversely no superlinear lower bound is known. (2) Is $q_{\mathrm{lin}}(p)$ the unique $q$ for which $f(n,p,q) = \Theta(n)$ (Problem 2 of the 1997 paper)? Sárközy and Selkow proved that for every $p \ge 6$ there is $\varepsilon > 0$ with $f(n,p,\binom{p}{2} - p + \lceil \log_2 p \rceil + 1) = \Omega(n^{1+\varepsilon})$, so by monotonicity all larger $q$ are superlinear. The open instances are therefore $p = 5$ — where the theorem does not apply and the sole value strictly between the thresholds $q_{\mathrm{lin}}(5) = 8$ and $q_{\mathrm{quad}}(5) = 10$ is $q = 9$, making part (1) the smallest instance of part (2) — and every $p \ge 9$, where the surviving candidates are $q_{\mathrm{lin}}(p) < q \le \binom{p}{2} - p + \lceil \log_2 p \rceil$. (For $p \le 4$ and $p \in \{6,7,8\}$ uniqueness is settled: every $q > q_{\mathrm{lin}}(p)$ is known to be superlinear or quadratic.) (3) Is $f(n,4,4) = \Theta(\sqrt{n})$; that is, can the gap between the Erdős–Gyárfás lower bound $f(n,4,4) \ge \sqrt{n} - 1$ and Mubayi's upper bound $f(n,4,4) \le n^{1/2+o(1)}$ be closed from either side? (4) Determine the leading constants at the thresholds for general $p$: (a) the constant $c_p$ in $f(n,p,q_{\mathrm{lin}}) = c_p n + o(n)$, currently sandwiched between $(3p-7)/(4p-10)$ and $1$ for $p \ge 3$ (exactly $5/6$ at $p = 4$ and $6/7$ at $p = 5$); (b) for even $p \ge 6$, the limit of $f(n,p,q_{\mathrm{quad}})/n^2$, which Bennett–Cushman–Dudek proved equivalent to determining the Brown–Erdős–Sós limits $F^{(4)}(n; p, 2p-1)$ — the maximum number of edges in a 4-uniform hypergraph on $n$ vertices containing no $p$ vertices that span $2p-1$ edges (known: $5/12$ at $p = 6$ and $p = 10$, $9/22$ at $p = 8$); and (c) the corresponding quadratic-threshold constants for odd $p$. (5) Geometric: must a planar $n$-point set in which every 4 points determine at least 5 distinct distances determine $\omega(n)$ distinct distances in total — that is, must $f_2(n,4,5)/n \to \infty$, where $f_2(n,p,q)$ is the minimum number of distinct distances determined by a planar $n$-point set in which every $p$ points determine at least $q$ distinct distances — given Tao's construction showing that $O(n^2/\sqrt{\log n})$ distances can suffice? Each of (1)–(5) is an independent open question and is separately resolvable; a resolution of one part—including the flagship case (1)—is not contingent on resolving the others, although a full solution of (2) would also settle (1) as its $p = 5$ instance.

References

1. P. Erdős and A. Gyárfás (1997). A variant of the classical Ramsey problem. Combinatorica 17(4), 459–467. doi:10.1007/BF01195000. https://doi.org/10.1007/BF01195000
2. D. Conlon, J. Fox, C. Lee, and B. Sudakov (2014). The Erdős–Gyárfás problem on generalized Ramsey numbers. Proceedings of the London Mathematical Society 110(1), 1–18 (2015). arXiv:1403.0250, doi:10.1112/plms/pdu049. https://arxiv.org/abs/1403.0250
3. C. Pohoata and A. Sheffer (2018). Local properties in colored graphs, distinct distances and difference sets. Combinatorica 39, 705–714 (2019). arXiv:1807.00201. https://arxiv.org/abs/1807.00201
4. S. Fish, C. Pohoata, and A. Sheffer (2018). Local properties via color energy graphs and forbidden configurations. SIAM Journal on Discrete Mathematics 34(1), 177–187 (2020). arXiv:1810.09019. https://arxiv.org/abs/1810.09019
5. J. Balogh, S. English, E. Heath, and R. A. Krueger (2021, revised 2022). Lower bounds on the Erdős–Gyárfás problem via color energy graphs. arXiv:2102.11466. https://arxiv.org/abs/2102.11466
6. A. Cameron and E. Heath (2020). New upper bounds for the Erdős–Gyárfás problem on generalized Ramsey numbers. arXiv:2006.09577. https://arxiv.org/abs/2006.09577
7. P. Bennett, R. Cushman, A. Dudek, and P. Prałat (2022). The Erdős–Gyárfás function $f(n,4,5) = \frac{5}{6} n + o(n)$ — so Gyárfás was right. arXiv:2207.02920. https://arxiv.org/abs/2207.02920
8. P. Bennett, A. Dudek, and S. English (2022, revised 2023). A random coloring process gives improved bounds for the Erdős–Gyárfás problem on generalized Ramsey numbers. arXiv:2212.06957. https://arxiv.org/abs/2212.06957
9. P. Bennett, M. Delcourt, L. Li, and L. Postle (2022, revised 2024). On generalized Ramsey numbers in the non-integral regime. arXiv:2212.10542. https://arxiv.org/abs/2212.10542
10. E. Gomez-Leos, E. Heath, A. Parker, C. Schwieder, and S. Zerbib (2023, revised 2024). New bounds on the generalized Ramsey number $f(n,5,8)$. arXiv:2308.16365. https://arxiv.org/abs/2308.16365
11. P. Bennett, R. Cushman, and A. Dudek (2023, revised 2024). Generalized Ramsey numbers at the linear and quadratic thresholds. arXiv:2309.00182. https://arxiv.org/abs/2309.00182
12. P. Bennett, R. Cushman, and A. Dudek (2024, revised 2025). The generalized Ramsey number $f(n,5,8) = \frac{6}{7} n + o(n)$. arXiv:2408.01535. https://arxiv.org/abs/2408.01535
13. T. Tao (2024). Planar point sets with forbidden $4$-point patterns and few distinct distances. arXiv:2409.01343. https://arxiv.org/abs/2409.01343
14. T. F. Bloom (ed.). Erdős Problem #135: must a planar point set in which any 4 points determine at least 5 distinct distances determine $\gg n^2$ distances? (Disproved by Tao, Lean-verified; the weaker superlinearity question remains open.) https://www.erdosproblems.com/135 (accessed 2026-09-06)
15. G. N. Sárközy and S. Selkow (2001). On edge colorings with at least q colors in every subset of p vertices. Electronic Journal of Combinatorics 8(1), R9. doi:10.37236/1553. https://doi.org/10.37236/1553
16. D. Mubayi (2004). An explicit construction for a Ramsey problem. Combinatorica 24(2), 313–324. doi:10.1007/s00493-004-0019-6. https://doi.org/10.1007/s00493-004-0019-6
17. F. Joos and D. Mubayi (2022). Ramsey theory constructions from hypergraph matchings. arXiv:2208.12563. https://arxiv.org/abs/2208.12563
18. T. F. Bloom (ed.). Erdős Problem #136: determine $f(n,4,5)$. (Solved: $f(n,4,5) \sim \frac{5}{6} n$; the page records the Erdős–Gyárfás disagreement on the answer.) https://www.erdosproblems.com/136 (accessed 2026-09-06)