Erdős problem #129 — quantified counterexample and exponential scale
Date: 2026-07-26 (UTC)
Claim labels
- (a) elementary-rigorous: proved here from definitions.
- (b) rigorous-modulo-named-theorem: the external theorem is named, linked, and checked in its primary source.
- (c) plausible/structural-unverified: an interpretation or possible intended repair, not a theorem.
- (d) computational-only: established by the accompanying finite exhaustive computation.
0. Mandatory live-page gate
(b) Before doing mathematics I fetched the live problem page, its LaTeX-source view, its bibliography popup, and all three comments through the Bright Data browser. The access date was 2026-07-26.
The page displayed:
- status OPEN (“open, and cannot be resolved with a finite computation”);
- 0 claimed proofs;
- “Currently working on this problem: None”;
- “Interested in collaborating: None”;
- all other work/difficulty/formalisation-interest markers: None;
- “Formalised statement? No”;
- a warning that the original source is ambiguous.
Thus the mandatory stop condition did not trigger: the page is not marked claimed-proof, solved, or falsified, and nobody is marked as currently working.
(b) Verbatim current statement (copied from the page's “View the LaTeX source”; only Markdown quote formatting was added):
> Let $R(n;k,r)$ be the smallest $N$ such that if the edges of $K_N$ are $r$-coloured then there is a set of $n$ vertices which does not contain a copy of $K_k$ in at least one of the $r$ colours. Prove that there is a constant $C=C(r)>1$ such that\[R(n;3,r) < C^{\sqrt{n}}.\]
Everything else listed on the live page
(b) The page attributes the conjecture to Erdős and Gyárfás and says they proved \(R(n;3,r)>C^{\sqrt n}\) for some \(C>1\). It notes that \(r=k=2\) recovers classical Ramsey numbers and records a broader conjectural formula.
(b) Crucially, the page already records Antonio Girão's objection: under the displayed definition, an independent uniform random red/blue colouring and \(\gg n^2\) edge-disjoint triangles give
\[ R(n;3,2)\ge C^n \]for some \(C>1\). The page explicitly says this contradicts the conjecture as written and speculates that Erdős may have intended a different, presently unclear problem.
(b) The three comments were:
1. Zach Hunter (2025-08-24): “yeah this problem still puzzles me.”
2. Przemek Chojecki (2026-02-28): a detailed random-colouring argument using a Steiner triple system for \(n\equiv1,3\pmod6\), giving \(\exp(c_r n)\) for infinitely many \(n\). The comment labels its write-up as GPT-5.2-generated.
3. Thomas Bloom (2026-02-28): this is exactly the objection already in the remarks, not a new GPT construction, and he has no further idea what was intended.
The discussion page itself says comments are unverified and still displays “0 claimed proofs.” I therefore did not treat the comment as a proof-claim marker, and I do not present the basic random-colouring objection as new.
1. Results obtained
1.1 A completely elementary quantified counterexample
(a) Theorem 1. For every integer \(n\ge500\),
\[ \boxed{\quad R(n;3,2)>\left\lfloor\left(\frac{511}{500}\right)^n\right\rfloor.\quad} \]In particular, the displayed \(C^{\sqrt n}\) upper bound is false already for \(r=2\).
The proof below is uniform in every \(n\ge500\), includes an explicit triangle decomposition, and has an exact rational arithmetic certificate in the checker.
1.2 A stronger consequence of a classical counting theorem
(b) Theorem 2. The Erdős--Kleitman--Rothschild enumeration theorem implies
\[ \boxed{\quad \liminf_{n\to\infty}\frac{\log_2 R(n;3,2)}{n}\ge\frac14, \quad} \]equivalently,
\[ R(n;3,2)\ge 2^{(1/4-o(1))n}. \]This strengthens the unspecified \(C^n\) objection on the live page. It is rigorous modulo the named 1976 theorem, whose primary paper was downloaded and checked.
1.3 An exact small case
(d) Exhaustion of all \(2^{10}\) labelled red/blue colourings of \(K_5\) and all \(2^{15}\) colourings of \(K_6\) gives
\[ \boxed{R(5;3,2)=6.} \]There are 260 labelled colourings of \(K_5\) in which the sole five-set contains both a red and a blue triangle, and there are none on \(K_6\) for which every five-set does.
2. Rewriting the negation correctly
Fix \(r=2\) and call an \(n\)-set \(S\) good if at least one colour has no triangle on \(S\). This is exactly the kind of set whose existence the definition of \(R(n;3,2)\) forces.
(a) Therefore a colouring of \(K_N\) witnesses
\[ R(n;3,2)>N \]if and only if every \(n\)-subset contains both a red triangle and a blue triangle. This quantifier reversal is the only logical reduction used below.
3. From-scratch triangle decomposition
Lemma 1: a Steiner triple system on every \(6t+3\) points
(a) Let \(q\) be odd and let the point set be
\[ V=\mathbb Z_q\times\mathbb Z_3. \]Since \(2\) is invertible modulo \(q\), define
\[ x\circ y=\frac{x+y}{2}\pmod q. \]Use the following triples:
1. for every \(x\in\mathbb Z_q\),
\[ \{(x,0),(x,1),(x,2)\}; \]
2. for every unordered \(x\ne y\) and every \(i\in\mathbb Z_3\),
\[ \{(x,i),(y,i),(x\circ y,i+1)\}. \]
These triples partition all pairs of points.
(a) Proof.
- Two points with the same first coordinate occur in their unique vertical triple.
- Two points with different first coordinates but the same second coordinate \(i\) occur in the unique triple indexed by their unordered first-coordinate pair and \(i\).
- Given \((x,i)\) and \((z,i+1)\) with \(x\ne z\), the other point in the unique possible triple is
\[ y=2z-x\pmod q, \]
because \(x\circ y=z\). It is distinct from both \(x\) and \(z\).
Thus every pair occurs exactly once. There are \(v=3q\) points and hence
\[ m=\frac{\binom v2}{3}=\frac{v(v-1)}6 \]edge-disjoint triangles. \(\square\)
Lemma 2: an almost-complete packing for every \(n\)
(a) Given any \(n\), let \(v\le n\) be the largest integer with
\[ v\equiv3\pmod6. \]Then \(v\ge n-5\), \(q=v/3\) is odd, and Lemma 1 supplies
\[ m=\frac{v(v-1)}6 \ge \frac{(n-5)(n-6)}6 \tag{1} \]edge-disjoint triangles on \(v\) of the \(n\) vertices. The remaining at most five vertices are simply unused.
This avoids appealing to the general existence theorem for Steiner triple systems and works uniformly for every \(n\).
4. Proof of the elementary exponential lower bound
Let
\[ b=\frac{511}{500}=1.022,\qquad N=\lfloor b^n\rfloor, \]and colour every edge of \(K_N\) independently red or blue with probability \(1/2\).
Fix an \(n\)-subset \(S\). Apply Lemma 2 inside \(S\), obtaining \(m\) edge-disjoint triangles.
(a) If \(S\) contains no red triangle, none of these \(m\) triangles can be all red. Each is all red with probability \(1/8\), and these events are independent because their edge sets are disjoint. Consequently,
\[ \Pr(S\text{ has no red triangle})\le\left(\frac78\right)^m. \]The identical estimate holds for blue, so
\[ \Pr(S\text{ is good}) \le2\left(\frac78\right)^m. \tag{2} \]Taking a union bound over all \(n\)-subsets and using
\(\binom Nn\le N^n\le b^{n^2}\),
\[ \Pr(\text{some good }S) \le 2b^{n^2}\left(\frac78\right)^{(n-5)(n-6)/6}. \tag{3} \]Put
\[ a=\log(8/7),\qquad \beta=\log(511/500), \]and
\[ F(n)= \frac{(n-5)(n-6)}6a-n^2\beta-\log2. \]The right side of (3) is at most \(e^{-F(n)}\).
(a) The standalone checker proves with exact rational intervals for logarithms that
\[ F(500)>1.00581385368, \] \[ F'(500)>0.248932769429, \qquad F''(n)=\frac a3-2\beta>0.000987480645 \quad\text{for all }n. \]Therefore \(F(n)>0\) for every real \(n\ge500\), and (3) is strictly less than \(1\). Some colouring consequently has no good \(n\)-set.
(a) The same checker verifies exactly that \(b^{500}\ge500\). Moreover,
\[ \frac{b^{n+1}/(n+1)}{b^n/n} =\frac{511n}{500(n+1)}>1 \]whenever \(11n>500\). Thus \(N\ge n\) for every \(n\ge500\), so the construction is non-vacuous. At the threshold,
\[ N=\lfloor1.022^{500}\rfloor=53143, \]and the explicit packing uses \(v=495\) vertices and
\[ m=\frac{495\cdot494}{6}=40755 \]edge-disjoint triangles.
It follows that \(R(n;3,2)>N\), proving Theorem 1.
Why this uniformly falsifies the requested bound
(a) For every fixed \(C>1\),
\[ \frac{1.022^n}{C^{\sqrt n}} =\exp\!\left(n\log1.022-\sqrt n\log C\right)\longrightarrow\infty. \]Hence \(\lfloor1.022^n\rfloor>C^{\sqrt n}\) for all sufficiently large \(n\). No choice of \(C=C(2)\) can satisfy the live statement.
Limit of the elementary packing method
(a) The same argument with any fixed
\[ 15. The \(1/4\) exponent from Erdős--Kleitman--Rothschild
Let \(T(n)\) be the number of labelled triangle-free graphs on \(n\) vertices.
(b) Erdős, Kleitman, and Rothschild prove
\[ \log_2 T(n)=\frac{n^2}{4}+o(n^2). \tag{4} \]Their stronger triangle case says almost all triangle-free graphs are bipartite.
Now return to a uniformly random red/blue colouring. On a fixed \(n\)-set \(S\), the red graph is uniform over all \(2^{\binom n2}\) labelled graphs. Therefore (4) gives
\[ \Pr(S\text{ has no red triangle}) =\frac{T(n)}{2^{\binom n2}} =2^{-n^2/4+o(n^2)}. \tag{5} \]The same holds for blue.
Fix any \(\gamma<1/4\) and take
\[ N=\lfloor2^{\gamma n}\rfloor. \]By (5), the expected number of good \(n\)-sets is at most
\[ 2\binom Nn\,2^{-n^2/4+o(n^2)} \le 2N^n\,2^{-n^2/4+o(n^2)} =2^{(\gamma-1/4)n^2+o(n^2)} \longrightarrow0. \]For all sufficiently large \(n\) this expectation is below \(1\), so a colouring with no good \(n\)-set exists. Since this holds for every \(\gamma<1/4\), Theorem 2 follows.
(b) This argument does not make the \(o(n^2)\) term effective; that is why the explicit elementary theorem remains useful.
6. Exponential order and what remains under the literal definition
(a) The classical diagonal Ramsey number gives
\[ R(n;3,2)\le R_2(n,n). \]Indeed, a red \(K_n\) contains no blue triangle, and a blue \(K_n\) contains no red triangle. The elementary Ramsey recurrence yields
\[ R_2(n,n)\le\binom{2n-2}{n-1}<4^{\,n-1}. \]Together with Theorem 1,
\[ R(n;3,2)=2^{\Theta(n)}. \]Together with Theorem 2, the bounds established here give
\[ \frac14 \le \liminf_{n\to\infty}\frac{\log_2R(n;3,2)}n \le \limsup_{n\to\infty}\frac{\log_2R(n;3,2)}n \le2. \tag{6} \]No claim is made that the constants in (6) are the best currently in the literature.
(c) Determining whether the normalized logarithm has a limit, or closing the constant gap in (6), is a coherent problem under the literal definition. It is not the \(C^{\sqrt n}\) problem printed on the page.
(c) The exact intended repair of Erdős's statement cannot responsibly be inferred. The live page itself calls the source ambiguous, and the original paper's full text was not retrievable in this environment. Guessing a modified quantifier or a different object would manufacture a new problem rather than solve #129.
7. Exact small-case computation
(d) A colouring witnesses \(R(5;3,2)>N\) precisely when every five-set has both colours of triangle.
- On \(K_5\), 260 of the \(2^{10}=1024\) labelled colourings qualify. One witness takes the triangle on vertices \(0,1,2\) red and every other edge blue.
- On \(K_6\), none of the \(2^{15}=32768\) labelled colourings qualifies.
Thus \(R(5;3,2)>5\) and \(R(5;3,2)\le6\), proving the computational-only equality \(R(5;3,2)=6\). A witness on any larger \(K_N\) would restrict to one on any six vertices, so the six-vertex nonexistence is the monotone cutoff.
This exact finite result is secondary; it is not used in either asymptotic proof.
8. Primary-source and literature audit
The cited 1997 source
(b) The live bibliography popup expands [Er97b] as:
> P. Erdős, Some old and new problems in various branches of combinatorics, Discrete Math. (1997), 227--231, MR 1439273.
The publisher/Crossref metadata verifies:
- Discrete Mathematics, volumes 165--166;
- 15 March 1997, pages 227--231;
- DOI 10.1016/S0012-365X(96)00173-200173-2).
(c) I could not verify the precise formulation inside the full paper. Direct ScienceDirect access returned a bot wall, its text-mining endpoint returned metadata only without an API key, and Bright Data refused the PDF path because that path is disallowed by the site's robots.txt. Exact-title and exact-notation searches found no accessible full-text copy. Consequently I make no claim about what alternate definition Erdős actually intended.
The enumeration theorem used here
(b) Primary source:
P. Erdős, D. J. Kleitman, and B. L. Rothschild,
Asymptotic enumeration of \(K_n\)-free graphs,
Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973),
Tomo II, Atti dei Convegni Lincei 17, Accad. Naz. Lincei, Rome (1976),
19--27, MR 0463020.
I checked the full nine-page scan. Its Corollary to Theorem 1 states the logarithmic enumeration of \(K_k\)-free labelled graphs (all logarithms in the paper are base 2); at \(k=3\) it is exactly (4). Theorem 2 states that almost all triangle-free graphs are bipartite.
A local copy is at
runs/references/erdos129/Erdos_Kleitman_Rothschild_1976.pdf, with SHA-256
184cf2838f0fa29c3e2eab9bdb6e200714de8ed501824f7a2e7350f6bf91efc7
Search result
(c) Searches for the exact notation \(R(n;k,r)\), the exact defining sentence, the title/DOI citation trail, and formulations involving induced triangle-free subgraphs found no primary source specifically studying the literal parameter beyond the 1997 source cited by the live page. This is an honest search miss, not proof that no such literature exists.
The only directly applicable stronger result found was the older Erdős--Kleitman--Rothschild counting theorem used above. No paper found in this search supplied an intended corrected statement for #129.
9. Independent verifier
(d) The standalone checker is
runs/erdos129_wave5j_verify.py.
It uses only the Python standard library and:
1. generates the explicit \(\mathbb Z_q\times\mathbb Z_3\) triangle systems;
2. checks every point-pair occurs exactly once;
3. performs the full \(v=495\), \(40755\)-block verification used at \(n=500\);
4. bounds \(\log(8/7)\), \(\log(511/500)\), and \(\log2\) by exact rational intervals from
\[ \log x=2\sum_{j\ge0}\frac{z^{2j+1}}{2j+1}, \qquad z=\frac{x-1}{x+1}; \]
5. certifies \(F(500)>0\), \(F'(500)>0\), and \(F''>0\), which verifies all infinitely many \(n\ge500\) rather than a finite scan;
6. exhausts all \(K_5\) and \(K_6\) colourings for the small case.
Reproduction:
python3 runs/erdos129_wave5j_verify.py
Observed output:
Elementary exponential-bound certificate: PASS
n0=500, v=495, edge-disjoint triangles=40755
rigorous lower bound for F(500): 1.00581385369
rigorous lower bound for F'(500): 0.248932769429
rigorous lower bound for F''(500): 0.000987480645149
Exact small-case exhaustive check: PASS
qualifying labelled K5 colourings: 260
one K5 red-edge witness: [(0, 1), (0, 2), (1, 2)]
qualifying labelled K6 colourings: 0
therefore R(5;3,2)=6 (computational-only classification)
ALL CHECKS PASSED
Checker SHA-256:
a8ce569d7a42d906a1a7c2aba05b8d15463b791f795aa5828bc3fc1fdc04a897
PROVED: Under the live page's literal definition, \(R(n;3,2)>\lfloor1.022^n\rfloor\) for every \(n\ge500\), and EKR strengthens this to \(R(n;3,2)\ge2^{(1/4-o(1))n}\); hence the requested \(C^{\sqrt n}\) upper bound is false as written.