Jumps of the density-Ramsey function $F^{(t)}(n,\alpha)$: does everything happen at $\alpha=0$? (Erdős #161)
Statement
Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the smallest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices so that whenever $X\subseteq [n]$ with $\lvert X\rvert \geq m$, at least $\alpha \binom{\lvert X\rvert}{t}$ of the $t$-subsets of $X$ receive each colour. For fixed $n,t$, as $\alpha$ increases from $0$ to $1/2$, does $F^{(t)}(n,\alpha)$ (viewed through its order of growth in $n$) increase continuously, or are there jumps? Is there only one jump? Note $\alpha=0$ recovers the usual Ramsey function: $F^{(t)}(n,0)$ is the least $m$ such that some $2$-colouring has no monochromatic $m$-set.
Acceptance. FULLY RESOLVES: a proof settling the jump structure for all $t$ (or at least all $t\geq 4$, where the mystery is open): either show that for every fixed $\alpha\in(0,1/2)$ the growth order of $F^{(t)}(n,\alpha)$ in $n$ is the same (up to $\alpha$-dependent constants in the exponent scale stated in the background), so the only jump is at $\alpha=0$ — or exhibit some $t$ and a threshold $\alpha_0\in(0,1/2)$ at which the order of growth changes, proving a second jump. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. A computation alone cannot close this. ADVANCES: extend the Conlon–Fox–Sudakov one-jump theorem from $t=3$ to $t=4$ (i.e. prove $F^{(4)}(n,\alpha)\ll_\alpha (\log n)^{1/3+o(1)}$ or any upper bound matching the lower-bound shape stated in the background); improve the general lower bound $(\log n)^{c_\alpha}$ to exponent $1/(t-1)$ with $c_\alpha$ independent of $\alpha$; determine how $c_\alpha$ behaves as $\alpha\to 0$ or $\alpha\to 1/2$; or exact values of $F^{(t)}(n,\alpha)$ for small $n$ with a reproducible exhaustive-search certificate, if accompanied by a structural conjecture they support. Deliver the proof file (or Lean sources), or for computational advances the search code plus certificates.
Background
Posed by Erdős [Er90b, p.21], who offered $500: 'If I can hazard a guess completely unsupported by evidence, I am afraid that the jump occurs all in one step at $0$. It would be much more interesting if my conjecture would be wrong and perhaps there is some hope for this for $t>3$. I know nothing and offer \$500 to anybody who can clear up this mystery.' Listed as open on erdosproblems.com/161 (fetched 2026-07-13, status 'open'); it is #40 in the Ramsey Theory section of the UCSD graphs problem collection. The known frontier: a conjecture of Erdős, Hajnal, and Rado (Erdős #562, erdosproblems.com/562) implies $F^{(t)}(n,0)\asymp \log_{t-1} n$ (the $(t-1)$-fold iterated logarithm), while results of Erdős and Spencer give $F^{(t)}(n,\alpha) \gg_\alpha (\log n)^{1/(t-1)}$ for every fixed $\alpha>0$, with a matching-shape upper bound for $\alpha$ near $1/2$ — so moving $\alpha$ off $0$ already jumps the growth from iterated-logarithmic to a power of $\log n$. Conlon, Fox, and Sudakov [CFS11] proved $F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}$ for any fixed $\alpha>0$, which together with the lower bound shows that for $t=3$ there is exactly one jump, at $\alpha=0$ — confirming Erdős's guess for $t=3$. For general $t$ and all $\alpha>0$ one has $F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}$. The case $t=2$ is discussed further at Erdős #563 (erdosproblems.com/563), and the graph companion asking for the precise asymptotic $F(n,\alpha)\sim c_\alpha\log n$ is Erdős #162 (erdosproblems.com/162). The attacker's tool: this is proof-shaped — stepping-up arguments, quasirandom or iterated-construction colourings for upper bounds, and probabilistic/discrepancy lower bounds; exact small-case values of $F^{(t)}(n,\alpha)$ computed via SAT for tiny $n,t$ can guide conjectures for $t=4$ but cannot close the asymptotic question.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #161 (T. F. Bloom) | website |
| REF-02 | Generalized hypergraph Ramsey — #40 in Ramsey Theory, UCSD graphs problem collection | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.