Erdős #563 — the graph (t=2) discrepancy-Ramsey function F(n,α) has order Θ_α(log n)

Statement

Let $F(n,\alpha)$ denote the smallest $m$ such that there exists a $2$-colouring of the edges of $K_n$ so that every $X\subseteq[n]$ with $\lvert X\rvert\geq m$ contains more than $\alpha\binom{\lvert X\rvert}{2}$ many edges of each colour.

Erdős's problem (as posed, [Er90b, p.21]; erdosproblems.com/563): prove that for every $0\leq\alpha<1/2$, $$F(n,\alpha)\sim c_\alpha\log n$$ for some constant $c_\alpha$ depending only on $\alpha$ — i.e. pin down the exact asymptotic constant. This sharp-constant question is still officially listed OPEN on erdosproblems.com (2 comments, last edited 18 Jan 2026).

What is solved (the subject of this page): the coarser order-of-growth statement $$F(n,\alpha)\;\asymp_\alpha\;\log n \qquad\text{for every fixed } 0\leq\alpha<1/2,$$ i.e. $F(n,\alpha)$ is sandwiched between two constant multiples of $\log n$. erdosproblems.com's own remarks state this directly: "It is easy to show via the probabilistic method that, for every $0\leq\alpha<1/2$, $F(n,\alpha)\asymp_\alpha\log n$." Only the sharp leading constant $c_\alpha$ in $F(n,\alpha)\sim c_\alpha\log n$ remains open — the order of magnitude is a closed, solved question, and it is this closed sub-result that downstream problems (see Related) build on.

Facts

- $\alpha=0$ recovers classical Ramsey numbers exactly. When $\alpha=0$, "more than $0$ edges of each colour in every $X$ of size $\geq m$" is just "no monochromatic clique of size $\geq m$," so $F(n,0)$ is the classical inverse-Ramsey function: $F(n,0)=\min\{m: R(m,m)>n\}$. erdosproblems.com states this identification explicitly on the page. This makes $\alpha=0$ the seed case from which the whole $\asymp_\alpha\log n$ family generalizes. - Origin of the general-$\alpha$ result: P. Erdős, J. Spencer, "Imbalances in k-colorations," *Networks* 1 (1971/72), 379–385 — the paper that generalizes Erdős's 1947 probabilistic lower-bound proof for Ramsey numbers ($R(k,k)>2^{k/2}$, via a random 2-colouring of $K_n$ and a union bound over monochromatic-clique events) from the "zero discrepancy" ($\alpha=0$) case to arbitrary fixed discrepancy $\alpha\in[0,1/2)$. - Both directions of the $\Theta$ are "probabilistic-method" arguments, but of different flavors: - *Upper bound* $F(n,\alpha)=O_\alpha(\log n)$ — an existence statement: exhibit one random $2$-colouring of $K_n$ that works for every large $X$ simultaneously. - *Lower bound* $F(n,\alpha)=\Omega_\alpha(\log n)$ — a universality statement: show *no* colouring, however cleverly chosen, can push the threshold below $c_\alpha\log n$; for $\alpha=0$ this is the classical counting bound $R(m,m)\leq\binom{2m-2}{m-1}<4^m$ on Ramsey numbers. - Numbering context (from the erdosproblems.com page itself and cross-checked against Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0?): #563 is catalogued as "#39 in Ramsey Theory" in the UCSD Erdős graph-problems collection (mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/GeneralizedRamsey.html); it sits numerically and thematically beside Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) (#38, the Erdős–Hajnal–Rado hypergraph-Ramsey growth-rate conjecture) and directly beneath Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? (#40, the same $F$-function generalized to $t$-uniform hypergraphs, $F^{(t)}(n,\alpha)$, of which #563 is exactly the $t=2$ instance). - Falsifiability: the *coarse* $\Theta_\alpha(\log n)$ statement is a fully closed, checkable mathematical fact (both bounds proved). The *remaining open* sharp-constant statement $F(n,\alpha)\sim c_\alpha\log n$ is, per erdosproblems.com's own disclaimer, "open, and cannot be resolved with a finite computation" — an asymptotic-limit claim, not a search problem.

Solution

Answer: $F(n,\alpha)=\Theta_\alpha(\log n)$ for every fixed $0\leq\alpha<1/2$ (Erdős–Spencer, *Networks* 1 (1972), building directly on Erdős's 1947 probabilistic Ramsey argument).

The transferable technique — random structure + large-deviation concentration + union bound, with the size threshold falling exactly at the crossover between "polynomially many things to worry about" and "exponentially-in-size$^2$ unlikely failure":

1. Randomize the object, not the search. Colour each edge of $K_n$ independently red/blue with probability $1/2$ each. This is Erdős's founding 1947 move (the literal birth of the probabilistic method in combinatorics), applied here one level up: instead of only asking "is there a monochromatic $K_m$," ask the finer question "does every sufficiently large vertex subset have a *reasonably balanced* colour split." 2. Bound the failure probability of one fixed witness with a large-deviation (Chernoff/Hoeffding-type) tail bound. For a fixed $X$ with $|X|=m$, the number of red edges inside $X$ is a sum of $\binom{m}{2}$ independent Bernoulli$(1/2)$ variables. Since $\alpha<1/2$ is bounded away from the mean fraction $1/2$, the probability that red (or blue) edges fall to $\leq\alpha\binom{m}{2}$ decays like $\exp(-c(\tfrac12-\alpha)^2 m^2)$ — quadratically in $m$, not just linearly. 3. Union-bound over all candidate witnesses, and note the crossover happens exactly at $m=\Theta(\log n)$. There are at most $n^{m}$ subsets of size $m$ to worry about (a term that is only *linear* in $m$ in its exponent, $\exp(m\log n)$), against a failure probability that is *quadratic* in $m$ in its exponent, $\exp(-c' m^2)$. These two exponents are equal, up to constant, exactly when $m\asymp\log n$ — below that scale the union bound explodes, above it it vanishes. This is the precise mechanical reason the answer is $\Theta(\log n)$ and not, say, $\Theta(\sqrt{\log n})$ or $\Theta((\log n)^2)$: the threshold size is wherever "count of substructures" (polynomial in $n$, i.e. linear-in-$m$ exponent) exactly balances "concentration of a size-$m$ statistic" (exponential-in-$m^2$), a crossover pattern that recurs any time a discrepancy/Ramsey-type quantity is pinned down by random-colouring + union bound. 4. The complementary lower bound comes from the opposite classical fact — that Ramsey numbers can't be avoided below scale $\log n$ either. For $\alpha=0$ this is the elementary counting bound $R(m,m)\le\binom{2m-2}{m-1}<4^m$: at $n\ge 4^m$, *every* colouring, however constructed, is forced to contain a fully monochromatic (zero-discrepancy) $K_m$, which certainly fails the "more than $\alpha$ fraction of each colour" requirement for any $\alpha\ge0$. So the same $\log n$ scale is unavoidable from below as well as achievable from above — squeezing $F(n,\alpha)$ into $\Theta_\alpha(\log n)$ from both sides. 5. **Reuse pattern — this is precisely the tool Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? plugs in as its base case.** Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? asks the identical question one level up: does $F^{(t)}(n,\alpha)$, the same discrepancy-Ramsey function for $t$-uniform hypergraphs, jump only at $\alpha=0$, for every $t$? The random-colouring + concentration + union-bound argument still runs for general $t$ — Erdős–Spencer's own lower bound $F^{(t)}(n,\alpha)\gg_\alpha(\log n)^{1/(t-1)}$ is the direct $t$-uniform generalization of the exact same crossover computation, except the failure-probability exponent scales like $m^{t-1}$ instead of $m^2$ once you're counting $t$-tuples inside an $m$-set instead of edges, which is *why* the growth rate degrades from a clean $\log n$ at $t=2$ to $(\log n)^{1/(t-1)}$ for general $t$. Conlon–Fox–Sudakov (arXiv:0901.3912) matched this lower bound with a genuine upper bound at $t=3$, fully closing that case too — but the underlying "randomize + Chernoff-type tail + union-bound crossover" idea, first cracked here at $t=2$, is exactly the transferable technique that the still-open general-$t$ case of Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? is trying to push further (their actual proof replaces the naive union bound with dependent-random-choice/hypergraph-container machinery, but the target scale it needs to hit is fixed by the same crossover logic).

Related

- Erdős #161 — does hypergraph discrepancy-Ramsey jump only at 0? — the direct hypergraph ($t$-uniform, general $t$) generalization of this exact function, $F^{(t)}(n,\alpha)$; #563 is precisely its $t=2$ special case, cited on the #161 page as "the $t=2$ graph analogue." The $t=3$ case is now itself fully resolved (Conlon–Fox–Sudakov, arXiv:0901.3912, $F^{(3)}(n,\alpha)\asymp_\alpha\sqrt{\log n}$); general $t\geq4$ remains open, with the growth-rate scaling first established here at $t=2$ as the template. - Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) — the Erdős–Hajnal–Rado hypergraph-Ramsey growth-rate conjecture, the $\alpha=0$ endpoint of the same $F^{(t)}$ family, numbered immediately adjacent to #563 in Erdős's own Ramsey-theory problem list (#38 vs #39). - concept/probabilistic-method — the founding Erdős 1947 random-colouring + union-bound technique for Ramsey lower bounds, of which this problem's upper-bound direction is the direct discrepancy-aware generalization. - concept/large-deviation-concentration — the Chernoff/Hoeffding-type tail bound on a sum of independent edge-colour indicators that makes step 2 of the argument work; the general machinery is covered in Alon–Spencer, *The Probabilistic Method*, 3rd ed. (Ch. 3 "Ramsey Numbers"/"Lower Bounds for Ramsey Numbers," Ch. 7 "Large Deviations"). - concept/ramsey-numbers — $F(n,0)$ is literally the inverse classical Ramsey function $\min\{m:R(m,m)>n\}$; this problem is the "positive-discrepancy" generalization of the classical two-sided ($4^m$ upper, $2^{m/2}$ lower) bound on $R(m,m)$.