Erdős Problem #183

Erdős Problem 183: super-exponential multicolour triangle Ramsey growth

1) Statement, attribution, and plan

Let $R_k=R(3;k)$ be the least $n$ for which every $k$-colouring of the edges of $K_n$ contains a monochromatic triangle. The question asks for $\lim_{k\to\infty}R_k^{1/k}$. Its value is now known to be $+\infty$. We reconstruct the coordinate-cover and palette recursion from Chapter 9 of the cited 2026 manuscript. We use parameters sufficient for the qualitative limit, rather than its stronger explicit lower bound. All construction steps needed for this limit are proved below; the construction is attributed to that source and is not claimed as new.

2) A pair of functions covering all pairs of words

Fix an integer $H\geq3$, and set $m=\lceil2H\log H\rceil$, $s=m(m+1)+1$. There is an $s$-by-$H^m$ matrix $D$ with entries in $[H]$, whose columns are indexed by $z\in[H]^m$, such that every $m+1$ columns contain all $H$ symbols in at least one row. To prove this, choose the entries independently and uniformly. For any fixed $m+1$ columns, a row fails with probability at most \[ H(1-1/H)^{m+1}<H\exp(-m/H)\leq H^{-1}. \] The probability all $s$ rows fail is at most $H^{-s}$. There are at most $H^{m(m+1)}$ choices of columns. The union bound makes the probability of any failure at most $H^{-1}<1$, proving existence.

This yields maps $f,g:[H]^s\to[H]^s$ such that, for any $x,y$, \[ x_d=f(y)_d\quad\hbox{or}\quad y_d=g(x)_d \quad\hbox{for some }d\in[s]. \tag{1} \] Indeed, let $\bar x=(x_1,\ldots,x_m)$ and set $g(x)_r=D_{r,\bar x}$. For fixed $y$, the exceptional columns \[ E_y=\{z:D_{r,z}\ne y_r\text{ for every }r\} \] number at most $m$, by the matrix property. List them in a fixed order as $z^{(1)},\ldots,z^{(\rho)}$ and put $f(y)_d=z^{(d)}_d$ for $d\leq\rho$, with arbitrary values thereafter. If $\bar x$ is not exceptional, the second equality in $1$ holds. Otherwise $\bar x=z^{(d)}$ for some $d\leq\rho\leq m$, and the first holds at that coordinate. This proves $1$.

3) Many mutually separated palettes

Let the integer $t\geq s$ tend to infinity, keeping $H,m,s$ fixed. For each $1\leq j\leq H$, choose a maximal family $\mathcal P_j$ of $t$-subsets of $[jt]$ whose distinct members satisfy $|P\setminus Q|=|Q\setminus P|\geq s$. Write $B_j=|\mathcal P_j|$. Maximality says every $t$-subset is within difference less than $s$ of a chosen one. A ball of this radius has size $\sum_{d=0}^{s-1}\binom td\binom{(j-1)t}d$, hence \[ B_j\geq \frac{\binom{jt}t}{\sum_{d=0}^{s-1}\binom td\binom{(j-1)t}d} \geq\frac{j^t}{s(jt^2)^{s-1}}. \tag{2} \] For the second inequality, each factor $(jt-r)/(t-r)$ in the binomial product is at least $j$, and each summand in the denominator is at most $(jt^2)^{s-1}$. Also $B_j\geq1$. A palette records colours omitted inside its associated block.

4) The recursive colouring and its invariant

We construct, for $0\leq j\leq H$, a triangle-free colouring on $n_j=\prod_{r=1}^j B_r$ vertices, using the $jt$ colours in $[jt]$. The stronger invariant is that the graph of edges of each one colour has a proper vertex-colouring with at most $j+1$ labels. For $j=0$, take one vertex and no edges.

At stage $j$, for each $P\in\mathcal P_j$ make a block $V_P$ carrying the previous construction, with its $(j-1)t$ colours relabelled by $[jt]\setminus P$. A colour is called active on this block when it is outside $P$, and missing when it belongs to $P$. For each active colour $c$, fix a proper $j$-label vertex-colouring $\ell^P_c:V_P\to[j]$ of its internal edges.

Order the palettes. For $P<Q$, choose distinct $a_1,\ldots,a_s\in Q\setminus P$ and distinct $b_1,\ldots,b_s\in P\setminus Q$. For $u\in V_P$, $v\in V_Q$, set \[ x(u)=(\ell^P_{a_d}(u))_{d=1}^s,\qquad y(v)=(\ell^Q_{b_d}(v))_{d=1}^s. \] These are words in $[H]^s$, since $j\leq H$. If some coordinate has $x(u)_d=f(y(v))_d$, colour $uv$ with $a_d$, choosing the first such coordinate. If none does, $1$ provides a coordinate with $y(v)_d=g(x(u))_d$; colour $uv$ with its $b_d$, again using the first. Every cross-edge colour lies in $P\mathbin\triangle Q$. Moreover, when the colour is active on one endpoint's block, its proper vertex label at that endpoint is fixed by the opposite endpoint.

There is no monochromatic triangle. Inside a block this follows by induction. For a triangle with two vertices in one block, suppose the two cross edges share colour $c$. If $c$ is missing on that block, its internal edge cannot have colour $c$. If $c$ is active, the cross-edge rule gives the two vertices the same $\ell_c$ label, so their internal edge again cannot have colour $c$. For a triangle in three blocks, colour $c$ on all cross edges would require its membership in the three palettes to differ on every pair. Three binary membership values cannot have that property.

Finally, for a fixed colour $c$, use the internal labels in $[j]$ on blocks where $c$ is active, and label $j+1$ on all blocks where it is missing. Internal $c$-edges are properly labelled by induction. A cross edge of colour $c$ joins one active block to one missing block, so its labels differ too. This proves the required $(j+1)$-label invariant and completes the induction.

5) Growth and the passage from a subsequence to a limit

At stage $H$ we have $k=Ht$ colours and $n_H=\prod_{j=1}^H B_j$ vertices with no monochromatic triangle. From $2$, \[ \log n_H\geq t\log(H!)-O_H(\log t). \] Consequently, for each fixed $H$, \[ \liminf_{t\to\infty}\frac{\log(R_{Ht}-1)}{Ht} \geq\frac{\log(H!)}H. \tag{3} \] These subsequences have arbitrarily large exponential bases, but one more argument ensures the limit over every colour count.

Put $N_k=R_k-1$. The usual block product gives $N_{a+b}\geq N_aN_b$: replace each vertex of a triangle-free $a$-colouring by a copy of a triangle-free $b$-colouring, using disjoint colour sets internally and between blocks. A triangle in one block is handled internally; one in three blocks projects to the outer colouring; one in two blocks uses both colour sets. Thus $u_k=\log N_k$ is superadditive and nonnegative. For fixed $r$, write $k=qr+h$, $0\leq h<r$. Repeated multiplication, with $N_0=1$ as an auxiliary convention, gives $u_k\geq q u_r$. It follows that $\liminf_k u_k/k\geq u_r/r$ for every $r$, while the limsup is at most $\sup_r u_r/r$. Hence $u_k/k$ has a limit in $[0,\infty]$. Equation $3$ bounds that limit below by $\log(H!)/H$ for every $H$. At least $H/2$ factors of $H!$ are at least $H/2$, so this bound tends to infinity. Therefore \[ \frac{\log(R_k-1)}k\longrightarrow\infty, \qquad R_k^{1/k}\longrightarrow\infty. \]

6) Outcome and sources

Outcome: SOLVED by reconstruction of the published construction. The probabilistic matrix, coordinate cover, palette packing, colouring invariant, and limiting argument have all been supplied. The standard finiteness of finite Ramsey numbers is the only background Ramsey fact used. This presentation does not claim the construction as original, does not reproduce the source's stronger quantitative rate, and has not been checked in a proof assistant.

• OpenAI, Ten Advances in Mathematics and Theoretical Computer Science, Chapter 9, "Super-exponential lower bounds for $R(3,\ldots,3)$", Sections 2--3 $2026$, https://cdn.openai.com/pdf/ten-proofs-oai.pdf.
• T. F. Bloom, Problem 183, https://www.erdosproblems.com/183, checked 23 September 2026.

The percentage measures the qualitative question proved above; it is not an estimate of independent discovery or formal-verification coverage.

7) COMPLETION ESTIMATE

COMPLETION: 100%

Erdős problem 183

1) FORMAL RESTATEMENT

Let $R(3;k)$ denote the smallest integer $n$ such that every $k$-edge-colouring of the complete graph $K_n$ contains a monochromatic triangle $K_3$. The problem asks to determine (or decide finiteness of) \[ \lim_{k\to\infty} R(3;k)^{1/k}. \] Equivalently: does there exist an absolute constant $C$ with $R(3;k)\le C^k$ for all large $k$?

2) QUICK LITERATURE/CONTEXT CHECK

I do not claim results beyond what is stated in the problem text. The statement records: (i) a pigeonhole recursion $R(3;k)\le 2+k(R(3;k-1)-1)$ implying $R(3;k)\le \lceil e\,k!\rceil$, (ii) exponential lower bounds via Schur numbers and later improvements.

3) ATTACK PLAN

Proof track. Prove the recursion and solve it explicitly to get the factorial upper bound. Disproof/construction track. Give an explicit $k$-colouring of $K_{2^k}$ with no monochromatic triangle, yielding an exponential lower bound.

4) WORK

Lemma 4.1 (Pigeonhole recursion).

For all integers $k\ge 2$, \[ R(3;k)\le 2+k\left(R(3;k-1)-1\right). \] Proof. Let $n=2+k(R(3;k-1)-1)$ and colour $E(K_n)$ with $k$ colours. Fix a vertex $v$. Among the $n-1$ edges incident to $v$, some colour (call it colour $1$) appears on at least \[ \left\lceil \frac{n-1}{k}\right\rceil =\left\lceil \frac{1+k(R(3;k-1)-1)}{k}\right\rceil =\left\lceil (R(3;k-1)-1)+\frac1k\right\rceil =R(3;k-1) \] edges. Let $U$ be the set of neighbours joined to $v$ in colour $1$, so $|U|\ge R(3;k-1)$.

If there is an edge of colour $1$ inside $U$, say $xy$, then $vxy$ is a monochromatic triangle of colour $1$. Otherwise, no edge inside $U$ has colour $1$, so the complete graph on $U$ is coloured using only the remaining $k-1$ colours. By the definition of $R(3;k-1)$, $K_U$ then contains a monochromatic triangle in one of those $k-1$ colours. Either way, a monochromatic triangle exists in $K_n$. Hence $R(3;k)\le n$. $\square$

Lemma 4.2 (Explicit solution of the recursion).

Define $b_k$ by $b_1=2$ and $b_k=k\,b_{k-1}+1$ for $k\ge 2$. Then \[ b_k=\sum_{i=0}^k \frac{k!}{i!}. \] In particular, \[ R(3;k)\le b_k+1 \le \lceil e\,k!\rceil. \] Proof. Divide the recurrence by $k!$: \[ \frac{b_k}{k!}=\frac{b_{k-1}}{(k-1)!}+\frac{1}{k!}. \] Iterating from $1$ to $k$ gives \[ \frac{b_k}{k!}=\frac{b_1}{1!}+\sum_{j=2}^k \frac{1}{j!}=2+\sum_{j=2}^k \frac{1}{j!}=\sum_{i=0}^k\frac1{i!}. \] Multiplying by $k!$ gives $b_k=\sum_{i=0}^k k!/i!$.

Now $e=\sum_{i=0}^\infty 1/i!$, so \[ e\,k!=\sum_{i=0}^k\frac{k!}{i!}+\sum_{i=k+1}^\infty \frac{k!}{i!}=b_k+\text{(tail)}. \] For $i\ge k+1$, $\frac{k!}{i!}=\frac{1}{(k+1)(k+2)\cdots i}$, hence the tail is $<\sum_{t\ge 1}(k+1)^{-t}=1/k<1$. Therefore $b_k=\lfloor e\,k!\rfloor$, so $b_k+1\le \lceil e\,k!\rceil$ and by Lemma 4.1, $R(3;k)\le b_k+1$. $\square$

Lemma 4.3 (Binary-string lower bound).

For every $k\ge 1$, \[ R(3;k)\ge 2^k+1. \] Proof. Let $V=\{0,1\}^k$ with $|V|=2^k$. For distinct $u,v\in V$, let $c(u,v)$ be the first coordinate $i\in\{1,\dots,k\}$ where $u_i\ne v_i$. This defines a $k$-edge-colouring of $K_{2^k}$.

Fix a colour $i$. Consider any triangle $u,v,w$. If $c(u,v)=i$, then $u$ and $v$ agree on coordinates $1,\dots,i-1$ and differ at $i$. For $c(v,w)$ also to be $i$, $v$ and $w$ must agree on $1,\dots,i-1$ and differ at $i$ as well, so $u_i=w_i$; thus $u$ and $w$ do not differ at coordinate $i$, and hence $c(u,w)\ne i$. Therefore no triangle is monochromatic. So $K_{2^k}$ admits a $k$-colouring with no monochromatic triangle, implying $R(3;k)>2^k$. $\square$

5) VERIFICATION

Recursion check: the key step is that if the neighbour-set $U$ has no internal colour-$1$ edges, its induced colouring uses only $k-1$ colours, so the definition of $R(3;k-1)$ applies. Binary construction check: for fixed $i$, each colour-$i$ class is a disjoint union of complete bipartite graphs (hence triangle-free).

6) FINAL

UNRESOLVED

(i) Strongest proved partial results here. We proved $2^k+1\le R(3;k)\le \lceil e\,k!\rceil$.

(ii) First gap. Show an absolute $C$ with $R(3;k)\le C^k$ for all large $k$ (or else prove $\lim R(3;k)^{1/k}=\infty$).

(iii) Top 3 next moves. 1. Prove a structural theorem: any partition of $E(K_n)$ into $k$ triangle-free graphs forces $n\le C^k$. 2. Improve lower bounds by explicit high-$k$ triangle-free edge partitions (algebraic constructions). 3. Computational search for improved small-$k$ behaviour might suggest a correct growth model.

(iv) Minimal counterexample structure (to finiteness). A family with $R(3;k)\ge \exp(\omega(k))$ (e.g. $\asymp k!$) would force $R(3;k)^{1/k}\to\infty$; one would expect near-extremal colour classes to resemble balanced blow-ups of sparse triangle-free graphs.