Erdős Problem #77

Erdős Problem 77: the exponential rate of diagonal Ramsey numbers

1. Statement and scope

2. Elementary upper and lower bounds

3. What lexicographic products actually give

4. Monotonicity and exponential bounds are insufficient

5. Assessment and attribution

Completion rate estimate: 10%.

1) FORMAL RESTATEMENT.

Let $k\in\mathbb{N}$ with $k\ge 1$. Let $R(k)$ denote the diagonal Ramsey number for $K_k$, i.e. \[ R(k)=\min\{n\in\mathbb{N}:\ \text{every red/blue colouring of }E(K_n)\text{ contains a monochromatic }K_k\}. \] Equivalently, $R(k)$ is the least $n$ such that every graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $k$.

The task is to determine the value of \[ \lim_{k\to\infty} R(k)^{1/k}, \] and in particular to prove that this limit exists (or to disprove existence by exhibiting nonconvergence).

Edge cases/conventions: $K_n$ is the complete simple graph on $n$ vertices; colourings are arbitrary functions $E(K_n)\to\{\text{red},\text{blue}\}$. The expression $R(k)^{1/k}$ is well-defined for $R(k)\ge 1$.

2) QUICK LITERATURE/CONTEXT CHECK.

Web browsing is available, but per the integrity rule I will only use results explicitly stated in the problem text. The problem text records Erdős' bounds $\sqrt2\le \liminf_{k\to\infty}R(k)^{1/k}\le \limsup_{k\to\infty}R(k)^{1/k}\le 4$, and notes that the upper bound $4$ has been improved (with specific numerical values and references given there). I do not reproduce those improved bounds here.

3) ATTACK PLAN.

Proof-track ideas (existence/value):

• Try to show (approximate) submultiplicativity or subadditivity of $\log R(k)$ to apply Fekete-type arguments and deduce existence of $\lim \frac1k\log R(k)$, hence existence of $\lim R(k)^{1/k}$.
• Improve asymptotic upper/lower bounds to squeeze the limit.

• Seek plausible oscillations by comparing $R(k)$ along different subsequences, e.g. even/odd, or around extremal constructions.

In this write-up I only establish the classical bounds $\limsup\le 4$ and $\liminf\ge \sqrt2$ with full proofs, and verify tiny cases computationally.

4) WORK.

Fast reality check (tiny $k$). A brute-force check over all $2$-colourings of $K_n$ for $n\le 6$ shows that $n=6$ is the least $n$ for which every colouring forces a monochromatic triangle, i.e. $R(3)=6$. Concretely, for $n=5$ the script found a colouring with red edges \[(0,3),(0,4),(1,2),(1,4),(2,3),\] which contains no monochromatic triangle, while for $n=6$ no such colouring exists. (Computation: exhaustive enumeration of all $2^{\binom{n}{2}}$ colourings for $n\le 6$.)

Lemma 77.1 (Binomial/$(4^{k})$ upper bound). For all integers $s,t\ge 1$, \[ R(s,t)\le \binom{s+t-2}{s-1}, \] where $R(s,t)$ is the least $n$ such that every red/blue colouring of $E(K_n)$ contains a red $K_s$ or a blue $K_t$. In particular, \[ R(k)=R(k,k)\le \binom{2k-2}{k-1}\le 4^{k-1}\qquad (k\ge 1). \]

Proof. We first prove the standard recursion \begin{equation}\label{wsref-0-65-71-3a-72-61-6d-73-65-79-2d-72-65-63} R(s,t)\le R(s-1,t)+R(s,t-1)\qquad (s,t\ge 2). \end{equation} Let $n:=R(s-1,t)+R(s,t-1)$. Consider any red/blue colouring of $E(K_n)$. Fix a vertex $v$. Let $A$ be the set of vertices joined to $v$ by a red edge, and $B$ those joined to $v$ by a blue edge. Then $|A|+|B|=n-1$.

If $|A|\ge R(s-1,t)$, consider the induced complete graph on $A$ with the inherited colouring. By definition of $R(s-1,t)$, it contains either a red $K_{s-1}$ or a blue $K_t$. In the first case, adding $v$ gives a red $K_s$ (because all edges from $v$ to $A$ are red). In the second case we already have a blue $K_t$.

If $|A|<R(s-1,t)$, then \[ |B|=n-1-|A|\ge (R(s-1,t)+R(s,t-1))-1-(R(s-1,t)-1)=R(s,t-1). \] Apply the same argument on $B$: the colouring on $K_B$ contains either a red $K_s$ or a blue $K_{t-1}$; in the latter case, adding $v$ produces a blue $K_t$.

Thus every colouring of $K_n$ contains a red $K_s$ or a blue $K_t$, proving (eq:ramsey-rec).

Now we prove by induction on $s+t$ that $R(s,t)\le \binom{s+t-2}{s-1}$ for all $s,t\ge 1$. Base cases: If $s=1$ or $t=1$ then $R(1,t)=R(s,1)=1$, while $\binom{s+t-2}{s-1}=\binom{t-1}{0}=1$ or $\binom{s-1}{s-1}=1$.

Induction step: assume $s,t\ge 2$ and the claim holds for all pairs $(s',t')$ with $s'+t'<s+t$. Then by (eq:ramsey-rec) and the induction hypothesis, \[ R(s,t)\le R(s-1,t)+R(s,t-1)\le \binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}=\binom{s+t-2}{s-1}, \] using Pascal's identity.

Setting $s=t=k$ yields $R(k)\le \binom{2k-2}{k-1}$. Finally, since \[ 2^{2k-2}=(1+1)^{2k-2}=\sum_{i=0}^{2k-2}\binom{2k-2}{i}\ge \binom{2k-2}{k-1}, \] we have $\binom{2k-2}{k-1}\le 2^{2k-2}=4^{k-1}$. $\square$

Lemma 77.2 (Probabilistic lower bound giving $\liminf\ge\sqrt2$). There exists $k_0\in\mathbb{N}$ (for instance $k_0=9$) such that for all $k\ge k_0$, \[ R(k) > 2^{k/2}. \] Consequently $\liminf_{k\to\infty} R(k)^{1/k} \ge \sqrt2$.

Proof. Fix $k\ge 9$ and let $n:=\lfloor 2^{k/2}\rfloor$. Consider a random red/blue colouring of $E(K_n)$ in which each edge is coloured red with probability $1/2$ and blue with probability $1/2$, independently.

For a fixed $k$-subset $S\subseteq [n]$, the induced $K_k$ on $S$ is monochromatic iff all $\binom{k}{2}$ edges are red or all are blue. Hence \[ \mathbb{P}(\text{$S$ spans a monochromatic }K_k)=2\cdot 2^{-\binom{k}{2}}=2^{1-\binom{k}{2}}. \] Let $X$ be the number of monochromatic $K_k$ subgraphs. By linearity of expectation, \[ \mathbb{E}X \le \binom{n}{k} \cdot 2^{1-\binom{k}{2}}. \] We use the standard bound $\binom{n}{k}\le (en/k)^k$ (which follows from $k!\ge (k/e)^k$). Thus \[ \mathbb{E}X \le 2\Big(\frac{en}{k}\Big)^k 2^{-\binom{k}{2}}. \] Since $n\le 2^{k/2}$, we have \[ \mathbb{E}X \le 2\Big(\frac{e 2^{k/2}}{k}\Big)^k 2^{-k(k-1)/2} =2\Big(\frac{e}{k}\Big)^k 2^{k/2}. \] For $k\ge 9$ we have $e/k\le 1/3$, so \[ \mathbb{E}X \le 2\Big(\frac{1}{3}\Big)^k 2^{k/2} = 2\Big(\frac{\sqrt2}{3}\Big)^k. \] Now $\sqrt2/3<1$, and already for $k=3$ we have $2(\sqrt2/3)^3<1$; therefore for all $k\ge 9$ the right-hand side is $<1$. Hence $\mathbb{E}X<1$, which implies there exists at least one colouring with $X=0$, i.e. with no monochromatic $K_k$. This means $R(k)>n$. Since $R(k)$ is an integer, $R(k)\ge n+1>2^{k/2}$.

Taking $k$-th roots and $\liminf$ gives $\liminf_{k\to\infty} R(k)^{1/k}\ge \sqrt2$. $\square$

Consequence (proved bounds). By Lemma 77.1, $\limsup_{k\to\infty}R(k)^{1/k}\le 4$. By Lemma 77.2, $\liminf_{k\to\infty}R(k)^{1/k}\ge \sqrt2$.

5) VERIFICATION.

• Quantifiers: Lemma 77.1 holds for all $s,t\ge 1$; diagonal case yields all $k\ge 1$.
• Union-size bound in Lemma 77.2: the probability calculation uses only independence of edge colours; the binomial bound and $e/k\le 1/3$ for $k\ge 9$ are explicit.
• Small cases: computationally verified $R(3)=6$ by exhaustive enumeration; Lemma 77.2 does not claim anything for $k<9$.

6) FINAL.

UNRESOLVED

(i) Strongest proved partial result: $\sqrt2\le \liminf_{k\to\infty}R(k)^{1/k}$ (Lemma 77.2) and $\limsup_{k\to\infty}R(k)^{1/k}\le 4$ (Lemma 77.1). Also a brute-force computation confirms $R(3)=6$.

(ii) First gap (crisp): Prove that the limit $\lim_{k\to\infty}R(k)^{1/k}$ exists (equivalently, prove $\liminf=\limsup$), or produce a rigorous construction showing nonconvergence.

(iii) Top 3 next moves (concrete):

1. Prove an inequality of the form $R(k+\ell)\le R(k)\,R(\ell)\,\poly(k,\ell)$ (or a comparable "almost submultiplicativity" for $\log R(k)$), then apply a Fekete-type lemma to deduce existence of $\lim \frac1k\log R(k)$.
2. Prove a complementary "almost supermultiplicativity" lower bound along some structured subsequence to control oscillations.
3. Computational/experimental: for small $k$ (e.g. $k\le 6$) compute best-known bounds on $R(k)$ and inspect $R(k)^{1/k}$ numerically to look for monotonicity or oscillation patterns; then try to reflect those patterns in theoretical inequalities.

(iv) Minimal counterexample structure (if the limit fails): there must exist two subsequences $k_i\to\infty$ and $\ell_i\to\infty$ with $\lim R(k_i)^{1/k_i}<\lim R(\ell_i)^{1/\ell_i}$, i.e. persistent exponential-rate oscillation. Any mechanism would likely require (a) different extremal constructions in different ranges of $k$, and (b) the absence of any near-submultiplicative control strong enough to force convergence.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - For $k\ge 2$, the diagonal Ramsey number $R(k)$ is the least integer $n$ such that every 2-coloring of the edges of $K_n$ contains a monochromatic copy of $K_k$. Equivalently, $R(k)$ is the least $n$ such that every graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $k$.

Question. Does the limit \[\lim_{k\to\infty} R(k)^{1/k}\] exist? If it exists, determine its value.

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. The problem statement lists a long history of upper bounds and notes Erdős proved $\sqrt2\le\liminf\le\limsup\le 4$. I will prove the classical $\sqrt2$ lower bound on $\liminf$ and the $4$ upper bound on $\limsup$ from scratch below, but I will not address the deeper improvements.

3) ATTACK PLAN Proof track ideas: 1. Prove subadditivity-type properties for $\log R(k)$ (if possible) to force existence of $\lim \frac{1}{k}\log R(k)$ by Fekete's lemma. 2. Improve upper/lower bounds on $\liminf,\limsup$.

Disproof track ideas: 1. Exhibit oscillation in $R(k)^{1/k}$ by proving different exponential rates along subsequences (no such phenomenon is known).

Chosen path in this attempt: establish two core inequalities with full proofs: an exponential lower bound via the probabilistic method and an exponential upper bound via the classic Ramsey recursion.

4) WORK Lemma 1 (Probabilistic lower bound: $R(k)$ is at least $\approx 2^{k/2}$). For every integer $k\ge 6$, \[R(k) > 2^{k/2}.\] Consequently, \[\liminf_{k\to\infty} R(k)^{1/k} \ge \sqrt{2}.\]

Proof. Fix $k\ge 6$ and set $n:=\lfloor 2^{k/2}\rfloor$. Consider a random red/blue coloring of the edges of $K_n$ where each edge is independently red with probability $1/2$ and blue with probability $1/2$.

For any fixed set $S$ of $k$ vertices, the probability that $S$ spans a red $K_k$ is $2^{-\binom{k}{2}}$, since all $\binom{k}{2}$ edges must be red. Similarly, the probability that $S$ spans a blue $K_k$ is $2^{-\binom{k}{2}}$. Thus the probability that $S$ spans a monochromatic $K_k$ (either color) is $2\cdot 2^{-\binom{k}{2}}$.

Let $X$ be the number of monochromatic $K_k$ subgraphs in the random coloring. By linearity of expectation, \[\mathbb E[X]=\binom{n}{k}\cdot 2\cdot 2^{-\binom{k}{2}}.\] Using the crude bound $\binom{n}{k}\le \frac{n^k}{k!}$, we get \[\mathbb E[X]\le \frac{n^k}{k!}\cdot 2\cdot 2^{-\binom{k}{2}}.\] Since $n\le 2^{k/2}$, this gives \[\mathbb E[X]\le \frac{(2^{k/2})^k}{k!}\cdot 2\cdot 2^{-\binom{k}{2}} =\frac{2^{k^2/2}}{k!}\cdot 2\cdot 2^{-(k^2-k)/2} =\frac{2^{1+k/2}}{k!}.\] For $k\ge 6$, one has $k!\ge 720$ and $2^{1+k/2}\le 2^{1+3}=16$, so $\mathbb E[X]\le 16/720<1$. Therefore there exists at least one coloring with $X=0$, i.e. with no monochromatic $K_k$. This means $R(k)>n\ge 2^{k/2}-1$, and in particular $R(k)>2^{k/2}$ for all $k\ge 6$.

Taking $k$th roots and letting $k\to\infty$ gives $\liminf_{k\to\infty} R(k)^{1/k}\ge \sqrt2$. $\square$

Lemma 2 (Classic recursion and exponential upper bound). Let $R(s,t)$ denote the off-diagonal Ramsey number (least $n$ such that every 2-coloring of $E(K_n)$ contains a red $K_s$ or a blue $K_t$). Then for integers $s,t\ge 2$, \[R(s,t)\le R(s-1,t)+R(s,t-1).\] Consequently, for $k\ge 2$, \[R(k)=R(k,k)\le \binom{2k-2}{k-1} < 4^{k-1},\] and hence \[\limsup_{k\to\infty} R(k)^{1/k}\le 4.\]

Proof. We first prove the recursion. Let \[N:=R(s-1,t)+R(s,t-1).\] Consider any red/blue coloring of the edges of $K_N$, and fix a vertex $v$. Let $R$ be the set of vertices joined to $v$ by a red edge, and $B$ the set joined to $v$ by a blue edge. Then $|R|+|B|=N-1$. If $|R|\ge R(s-1,t)$, then by definition of $R(s-1,t)$ the induced coloring on $K_R$ contains either a red $K_{s-1}$ or a blue $K_t$. In the first case, adding $v$ produces a red $K_s$; in the second case we already have a blue $K_t$. Similarly, if $|B|\ge R(s,t-1)$, then inside $B$ there is either a red $K_s$ or a blue $K_{t-1}$; in the second case adding $v$ gives a blue $K_t$.

Since $|R|+|B|=N-1=(R(s-1,t)-1)+(R(s,t-1)-1)+1$, at least one of the inequalities $|R|\ge R(s-1,t)$ or $|B|\ge R(s,t-1)$ must hold. Thus every coloring of $K_N$ contains a red $K_s$ or a blue $K_t$, proving $R(s,t)\le N$.

Now prove the binomial bound by induction on $s+t$. The base cases $R(1,t)=R(s,1)=1$ satisfy $1=\binom{s+t-2}{s-1}$ when one parameter is $1$. Assuming $R(s-1,t)\le \binom{s+t-3}{s-2}$ and $R(s,t-1)\le \binom{s+t-3}{s-1}$, the recursion gives \[R(s,t)\le \binom{s+t-3}{s-2}+\binom{s+t-3}{s-1}=\binom{s+t-2}{s-1}\] by Pascal's identity. Setting $s=t=k$ yields $R(k)\le \binom{2k-2}{k-1}$. Finally, $\binom{2k-2}{k-1}\le 2^{2k-2}=4^{k-1}$, giving $\limsup R(k)^{1/k}\le 4$. $\square$

FAST REALITY CHECK For small $k$, one knows exact values only for a few $k$, and brute-force computation grows infeasible quickly. The two lemmas above give the classic exponential window \[\sqrt2\ \le\ \liminf R(k)^{1/k}\ \le\ \limsup R(k)^{1/k}\ \le\ 4,\] matching the statement in the problem text (at a coarse level).

5) VERIFICATION - Lemma 1: the expectation bound is explicit and uses only $\binom{n}{k}\le n^k/k!$ and $k!\ge 720$ for $k\ge 6$. - Lemma 2: the recursion argument with a pivot vertex is standard; the induction to $\binom{2k-2}{k-1}$ uses only Pascal's identity.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved from scratch the classical exponential bounds \[2^{k/2} < R(k) < 4^k\quad\text{(up to constant factors)}\] for all large $k$, yielding $\sqrt2\le \liminf R(k)^{1/k}$ and $\limsup R(k)^{1/k}\le 4$ (Lemmas 1--2).

(ii) First gap: Prove that $R(k)^{1/k}$ actually converges, i.e. show \[\liminf_{k\to\infty} R(k)^{1/k}=\limsup_{k\to\infty} R(k)^{1/k}.\] The standard recursion gives upper bounds but does not provide a subadditivity property strong enough to force existence of the limit.

(iii) Top 3 next moves (concrete): 1. Seek an inequality relating $R(k+\ell)$ to $R(k)$ and $R(\ell)$ that is close enough to multiplicativity/submultiplicativity to imply existence of $\lim \frac{1}{k}\log R(k)$ via an (almost) subadditive lemma. 2. Improve the exponential upper bound constant (known improvements exist per the problem text) and see whether the methods can also yield structural control that might imply convergence. 3. Investigate whether the lexicographic/tensor product constructions for lower bounds give any supermultiplicativity properties for the inverse Ramsey function that could translate into convergence information.

(iv) What a minimal counterexample would likely look like (structure/parameters): A scenario where along two subsequences $k_i$ and $k'_j$, the ratios $\frac{1}{k_i}\log R(k_i)$ and $\frac{1}{k'_j}\log R(k'_j)$ converge to different limits, forcing $R(k)^{1/k}$ to oscillate between two distinct constants.