ERDŐS/DAILY ▸

← back to the ledger

ERDőS #165 · PARTIAL

Erdős problem #165 — live audit, exact order-\(\le 13\) computation, and the remaining asymptotic wall

Date: 2026-07-26 UTC

Required verifier: runs/erdos165_wave5l_reverify.py

Verifier SHA-256: 1dca215518302e7f7edf9bb82e72b9af20983e52dbf6c828b97c3d8b3e130ac9

Claim labels

No novelty claim is made for a fact merely because it was recomputed here.

0. Mandatory live-page gate

I fetched both the live problem page and its linked discussion thread through the Bright Data remote-browser route. Direct datacenter HTTP was not used as a substitute.

The live statement, verbatim, is:

> Give an asymptotic formula for \(R(3,k)\).

Live-page observations at access time:

The live page states the following current mathematical window:

\[ (c+o(1))\frac{k^2}{\log k}\le R(3,k) \le (1+o(1))\frac{k^2}{\log k} \]

for some \(c>0\). It attributes the order-of-magnitude lower bound to Kim and the upper bound to Shearer, improving Ajtai–Komlós–Szemerédi. It records the successive lower constants \(1/162\), \(1/4\), \(1/3\), and currently \(1/2\), with the latest bound due to Hefty–Horn–King–Pfender. It says the \(1/2\) constant is conjectured to be the answer.

The five comments contain:

1. Alfaiz (2025-10-01): links the Campos–Jenssen–Michelen–Sahasrabudhe \(1/3\) paper; marked as incorporated into the page.

2. zach hunter (2025-10-09): notes that those authors conjecture \(1/2\).

3. gdahia (2025-10-23): links the Hefty–Horn–King–Pfender \(1/2\) paper; marked as incorporated into the page.

4. Alfaiz (2025-12-01): reports that the AKS reference would not load; marked as addressed.

5. wes (2026-06-10): says, “This paper has a Lean formalization linked here,” and links https://www.math.cmu.edu/~wes/trellis.php. The comment does not claim a proof of problem #165.

Thus neither stop condition was present: there was no claimed proof/solved/falsified status and no current worker.

1. Primary-source audit

The source verifier downloads the arXiv TeX, rather than trusting search-result summaries.

\[ R(3,k)\ge\left(\frac12+o(1)\right)\frac{k^2}{\log k} \]

and, equivalently on the construction side, triangle-free \(n\)-vertex graphs with

\[ \alpha(G)<(1+\varepsilon)\sqrt{n\log n} \]

for all sufficiently large \(n\).

\[ \alpha(G)\ge n\,\frac{d\log d-d+1}{(d-1)^2}. \]

This gives the current \(1+o(1)\) Ramsey upper constant.

\[ \frac{\alpha(G)}{\overline\alpha_G(1)}\ge\frac43 \]

for every triangle-free \(G\). Their Conjectures 2 and 3 would each imply

\[ R(3,k)\le\left(\frac12+o(1)\right)\frac{k^2}{\log k}. \]

I also searched exact author/title combinations, \(R(3,k)\) with 2025–2026 date terms, and checked Robert Morris’s 2026 survey arXiv:2601.05221. I found no primary source claiming a better upper constant or a resolution. An attempted broad arXiv API query received HTTP 429, so this is an honest search report, not a proof that no unindexed paper exists.

2. Exact reduction of the open problem

Define

\[ a(n)=\min\{\alpha(G): |V(G)|=n,\;G\text{ triangle-free}\}. \]

2.1 Exact inverse relation

[a]

\[ R(3,k)=\min\{n:a(n)\ge k\}. \]

This is the definition of \(R(3,k)\) rewritten in triangle-free language. Also, \(a(n)\) is nondecreasing: deleting a vertex from any \((n+1)\)-vertex graph cannot increase its independence number, so minimizing after deletion gives \(a(n)\le a(n+1)\).

2.2 Conversion of asymptotic constants

[a] If

\[ a(n)=(A+o(1))\sqrt{n\log n}, \]

then

\[ R(3,k)=\left(\frac{1}{2A^2}+o(1)\right)\frac{k^2}{\log k}. \]

Indeed, for \(n=(C+o(1))k^2/\log k\),

\[ \log n=(2+o(1))\log k,\qquad \sqrt{n\log n}=(\sqrt{2C}+o(1))k. \]

The inverse threshold is therefore \(A\sqrt{2C}=1\), or \(C=1/(2A^2)\).

2.3 What the known bounds say about \(a(n)\)

[b] The HHKP construction gives

\[ a(n)\le(1+o(1))\sqrt{n\log n}. \]

[b] Shearer plus the elementary neighborhood bound gives

\[ a(n)\ge\left(\frac1{\sqrt2}-o(1)\right)\sqrt{n\log n}. \]

Here is the constant calculation. If \(d\) is the average degree, then a largest neighborhood is independent, so

\[ \alpha(G)\ge\Delta(G)\ge d. \]

Shearer gives

\[ \alpha(G)\ge(1+o(1))\frac{n\log d}{d}. \]

Writing \(d=x\sqrt{n\log n}\), one has \(\log d=(1/2+o(1))\log n\) in the critical range, and hence

\[ \frac{\alpha(G)}{\sqrt{n\log n}} \ge (1-o(1))\max\left\{x,\frac1{2x}\right\}. \]

The right side is minimized at \(x=1/\sqrt2\), with value \(1/\sqrt2\). Degrees outside the critical range only make one of the two bounds larger.

Consequently the exact present gap is

\[ \left(\frac1{\sqrt2}-o(1)\right)\sqrt{n\log n} \le a(n)\le (1+o(1))\sqrt{n\log n}. \]

2.4 The exact missing lemma

[a, reduction] In view of HHKP, the conjectured answer

\[ R(3,k)=\left(\frac12+o(1)\right)\frac{k^2}{\log k} \]

would follow from—and is equivalent to—the uniform lower bound

\[ \boxed{\alpha(G)\ge(1-o(1))\sqrt{n\log n} \quad\text{for every triangle-free \(n\)-vertex graph \(G\)}.} \]

[b] Either DJPR Conjecture 2 or Conjecture 3 supplies this missing upper-side ingredient by their stated lemma.

[a] Combining only the neighborhood and Shearer inequalities cannot reach it: their optimized constant is exactly \(1/\sqrt2\). A successful proof must inject information not present in that two-bound optimization.

3. Exact finite computation

Let

\[ P_G(x)=\sum_j i_j(G)x^j \]

be the independence polynomial. Put

\[ Z=P_G(1),\qquad S=P'_G(1),\qquad \mu(G)=\frac{S}{Z}, \qquad \rho(G)=\frac{\alpha(G)}{\mu(G)}. \]

Thus \(\mu(G)\) is the mean size of a uniformly random independent set. DJPR Conjecture 1 is \(\rho(G)\ge4/3\) for every triangle-free graph.

3.1 Exhaustive result

[d] Every unlabeled triangle-free graph through 13 vertices was enumerated with nauty 2.8.8 geng -t. A separate Python graph6 decoder:

1. checks triangle-freeness again;

2. recomputes \((\alpha,Z,S)\) from the recurrences

\[ Z(H)=Z(H-v)+Z(H-N[v]), \]

\[ S(H)=S(H-v)+S(H-N[v])+Z(H-N[v]); \]

3. computes \(\rho=\alpha Z/S\) as an exact rational.

The exact table is:

| \(n\) | triangle-free classes | \(a(n)\) | classes with \(\alpha=a(n)\) | \(\min\rho(G)\) | independence polynomial of the unique ratio minimizer |

|---:|---:|---:|---:|---:|:---|

| 1 | 1 | 1 | 1 | \(2\) | \(1+x\) |

| 2 | 2 | 1 | 1 | \(3/2\) | \(1+2x\) |

| 3 | 3 | 2 | 2 | \(12/7\) | \(1+3x+2x^2\) |

| 4 | 7 | 2 | 3 | \(3/2\) | \(1+4x+4x^2\) |

| 5 | 14 | 2 | 1 | \(22/15\) | \(1+5x+5x^2\) |

| 6 | 38 | 3 | 15 | \(3/2\) | \(1+6x+12x^2+8x^3\) |

| 7 | 107 | 3 | 9 | \(99/67\) | \(1+7x+15x^2+10x^3\) |

| 8 | 410 | 3 | 3 | \(117/80\) | \(1+8x+18x^2+12x^3\) |

| 9 | 1,897 | 4 | 290 | \(132/89\) | \(1+9x+29x^2+40x^3+20x^4\) |

| 10 | 12,172 | 4 | 313 | \(22/15\) | \(1+10x+35x^2+50x^3+25x^4\) |

| 11 | 105,071 | 4 | 105 | \(556/381\) | \(1+11x+40x^2+58x^3+29x^4\) |

| 12 | 1,262,180 | 4 | 12 | \(161/111\) | \(1+12x+46x^2+68x^3+34x^4\) |

| 13 | 20,797,002 | 4 | 1 | \(244/169\) | \(1+13x+52x^2+78x^3+39x^4\) |

Every row’s ratio minimizer is unique up to isomorphism.

It follows that:

[d]

\[ \rho(G)\ge\frac{244}{169} =1.4437869822\ldots>\frac43 \]

for every triangle-free graph on at most 13 vertices. Thus DJPR Conjecture 1 is verified in this complete finite regime. The margin is

\[ \frac{244}{169}-\frac43=\frac{56}{507}. \]

DJPR report a 35-vertex cyclic Ramsey graph with ratio approximately \(1.43283\), so the order-\(\le13\) margin should not be extrapolated asymptotically.

3.2 Why the filtered enumeration is exhaustive

[b] DJPR Theorem 6 proves, for every graph,

\[ \rho(G)\ge1+\frac{\alpha(G)}n. \]

For each \(n\), the verifier first checks an explicit candidate ratio \(r_n\). It then scans every graph with

\[ 1+\frac{\alpha(G)}n\le r_n. \]

Every omitted graph has a strictly larger certified lower bound and cannot be a minimizer. At \(n=13\), this leaves all 275,086 classes with \(\alpha\le5\), out of 20,797,002 total classes. The Python code recomputes \(\alpha\) on every emitted graph.

As a separate check not using isomorphism rejection, a pure-Python vertex-augmentation algorithm generated every labeled triangle-free graph through \(n=7\). Its counts were

\[ 1,2,7,41,388,5789,133501, \]

and it independently reproduced every minimum ratio through that order. An unpruned scan of all 1,262,180 order-12 classes also reproduced the row before the optimized verifier was packaged.

4. Explicit extremal construction at \(n=13\)

Let \(G\) have vertex set \(\mathbb Z_{13}\), joining \(u\) and \(v\) when

\[ v-u\in D=\{1,5,8,12\}=\{\pm1,\pm5\}\pmod {13}. \]

4.1 Triangle-free

[a] Direct modular addition gives

\[ D+D=\{0,2,3,4,6,7,9,10,11\}, \]

which is disjoint from \(D\). A triangle translated to contain \(0\) would require \(x,y,y-x\in D\), equivalently a sum of two elements of \(D\) lying in \(D\). Hence no triangle exists.

4.2 Independence number exactly four

[a] The set \(\{0,2,4,6\}\) is independent, so \(\alpha(G)\ge4\).

Suppose five vertices were independent and list their five positive cyclic gaps. Difference \(1\) is forbidden, so every gap is at least \(2\), and the gaps sum to \(13\). Subtracting \(2\) from each gap leaves five nonnegative integers summing to \(3\). There are only three partition types:

In all cases, one gap or two consecutive gaps sum to \(5\). The corresponding two selected vertices differ by \(5\), hence are adjacent. Contradiction. Therefore \(\alpha(G)=4\).

This construction alone gives the familiar lower bound \(R(3,5)\ge14\). The exhaustive computation further shows that this is the unique triangle-free 13-vertex graph with independence number four.

4.3 Exact independent-set data

[d] Direct enumeration of its \(2^{13}=8192\) vertex subsets gives

\[ P_G(x)=1+13x+52x^2+78x^3+39x^4. \]

Thus

\[ Z=183,\qquad S=507,\qquad \mu=\frac{507}{183}=\frac{169}{61}, \]

and

\[ \rho(G)=\frac4{169/61}=\frac{244}{169}. \]

5. Reproduction

The verifier uses Python’s standard library plus nauty:

sudo apt-get install nauty
python runs/erdos165_wave5l_reverify.py --sources

The completed run ended with:

Nauty-backed exact tables passed: inverse Ramsey through n=13; ratio through n=13; unpruned=False.
Primary-source audit passed: HHKP arXiv:2510.19718v3, CJMS arXiv:2505.13371, DJPR arXiv:1606.01043v2, and Shearer DOI metadata.
ALL ERDOS #165 REVERIFICATION CHECKS PASSED

The verifier contains:

6. Precise wall

The finite result does not resolve an asymptotic problem.

1. [a] The exact missing statement is the uniform bound

\[ \alpha(G)\ge(1-o(1))\sqrt{n\log n} \]

for every triangle-free \(G\).

2. [a] Shearer plus the neighborhood bound stalls at the smaller constant \(1/\sqrt2\); the optimization above identifies exactly where.

3. [b] The DJPR hard-core expectation theorem by itself has the same Shearer-scale strength. Their maximum/average Conjecture 2 or fugacity Conjecture 3 is the additional lemma that would bridge the factor.

4. [c] The HHKP examples make the desired bound structurally plausible: their independence number is asymptotic to \(\sqrt{n\log n}\). This is evidence, not an upper-bound proof for arbitrary triangle-free graphs.

5. [a] No finite graph enumeration can supply the missing uniformity in \(n\).

For scale, there are 467,871,369 unlabeled triangle-free graphs on 14 vertices, versus 20,797,002 on 13. At the measured order-13 throughput, merely streaming and classifying order 14 is estimated at about 0.3 core-hours; recomputing the ratio table is roughly 0.5–1 core-hour depending on the usable independence-number cutoff. At a typical \(US\$0.05\)–\(0.12\) per vCPU-hour this is inexpensive in money but outside the “few CPU-minutes” rule. More importantly, it would add only another finite row and would not attack the missing asymptotic lemma.

PARTIAL: Exhaustively verified the exact inverse-Ramsey and maximum/average independent-set tables for every triangle-free graph through 13 vertices (unique minimum ratio \(244/169>4/3\)), isolated the equivalent missing bound \(\alpha(G)\ge(1-o(1))\sqrt{n\log n}\), and did not solve the uniform asymptotic problem.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger