Erdoes #620 - working report - Erdős Problem a Day

Erdős problem #620 — wave w003

Access date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved directly here.
(b) rigorous-modulo-named-theorem: the exact named input is stated.
(c) plausible/structural-unverified: not used as a theorem.
(d) computational-only: a finite exhaustive calculation with a

reproducible checker.

0. Mandatory live-page check

I fetched the rendered live problem page, its /latex/620 view, and its discussion thread through the Bright Data browser path. Direct datacenter curl returned the Cloudflare “Just a moment...” page, so it was not used as the source.

Live badge: OPEN.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
“Likes this problem,” “looks difficult,” “looks tractable,” “results could be

formalisable,” and “working on formalising”: all None.

The gate therefore permits work: the page shows neither a claimed

proof/solved/falsified status nor a current worker.

Verbatim current statement

Copied from the live /latex/620 view:

If $G$ is a graph on $n$ vertices without a $K_4$ then how large a triangle-free induced subgraph must $G$ contain?

The page then defines $f(n)$ to be the guaranteed size and calls this the Erdős--Rogers problem.

Known results listed on the live page

The page says:

f(n)=n^{1/2+o(1)}.

It attributes the following historical bounds:

n^{1/2}\ll f(n)\ll n^{7/10+o(1)} \quad\text{(Bollobás--Hind),}

n^{1/2}(\log\log n)^{1/2}\ll f(n) \ll n^{2/3}(\log n)^{1/3} \quad\text{(Krivelevich),}

and

f(n)\ll n^{1/2}(\log n)^{120} \quad\text{(Wolfovitz).}

Its displayed “best bounds currently known” are

n^{1/2}\frac{(\log n)^{1/2}}{\log\log n} \ll f(n)\ll n^{1/2}\log n,

with the lower bound attributed to Shearer and the upper bound to Mubayi and Verstraëte.

There is one comment, by Zach Hunter at 11:34 on 2025-09-01. It points to arXiv:2401.02548, states its $O(\sqrt n\log n)$ upper bound, and notes the Shearer lower bound $\sqrt{n\log n}/\log\log n$. The thread says the site was updated in response and warns that comments are unverified.

Thus the live-page status and baseline were fully checked before doing any mathematics.

1. Normalisation

For a graph $G$, write

\alpha_3(G)=\max\{|S|:S\subseteq V(G),\ G[S]\text{ is triangle-free}\}.

Then the question's function is

f(n)=\min\{\alpha_3(G): |V(G)|=n,\ G\text{ is }K_4\text{-free}\}. \tag{1}

Calling the subgraph “induced” causes no mismatch: a vertex set is triangle-free precisely when the subgraph it induces has no triangle.

2. Primary-source literature check: a new result settles the order

2.1 The page's cited upper bound

(b) The identifier on the page exists. Dhruv Mubayi and Jacques Verstraëte, On the order of Erdős--Rogers functions, arXiv:2401.02548v2, states for every fixed

$s\ge3$

f_{s,s+1}(n)=O(\sqrt n\log n).

The published version is On the order of the classical Erdős--Rogers functions, Bull. London Math. Soc. 57 (2025), 582--598, DOI 10.1112/blms.13214.

2.2 The new primary source

Targeted searches for the exact function, problem name, and recent arXiv records found a source eleven days newer than the live page's displayed state:

Robert Morris, Julian Sahasrabudhe, Jacques Verstraëte,

On the Erdős--Rogers function, arXiv:2607.16118v1.

The arXiv record says submitted 2026-07-17 16:56:28 UTC, version v1,

22 pages. There is no later version as of the access date.

I downloaded and read the actual PDF and TeX source. The PDF SHA-256 is

b2e140d9831b53fb1140735039fd1a02c60c93ec59c0ac5938ae95b4b25835a2; the source-tar SHA-256 is 8b04102f789d44a4264784fd0a60f18215a6bd24abc5b3cfe6d7af64a5047228.

Its Theorem 1.1 is:

f_{s,s+1}(n)=\Theta(\sqrt{n\log n}) \quad\text{for every fixed }s\ge2. \tag{2}

More importantly for the uniformity/finiteness audit, its quantitative Theorem 3.1 says that there is an absolute $C>0$ such that, for every $s\ge2$ and every $n\ge s^C$, an $n$-vertex $K_{s+1}$-free graph exists in which every set of

k\ge Cs^3\sqrt{n\log n}

vertices contains a $K_s$. This is for every sufficiently large $n$, not merely a subsequence of admissible orders. Setting $s=3$ gives

f(n)=O(\sqrt{n\log n}). \tag{3}

This is (b): rigorous modulo the named v1 preprint theorem. I do not silently elevate a new unrefereed preprint to an independently re-proved theorem.

2.3 Direct check of the lower-bound reduction

The new paper invokes Corollary 2 of:

Gwenaël Joret, Piotr Micek, Bruce Reed, Michiel Smid,

Tight Bounds on the Clique Chromatic Number, Electron. J. Combin. 28(3) (2021), #P3.51, DOI 10.37236/9659, arXiv:2006.11353v2.

I checked the published PDF (SHA-256 d12e3f99bac8c2223904498de56dc4c50c1adfbe619284cf05f34b1418eb6cd8). Its Corollary 2 states that every $n$-vertex graph has clique chromatic number

O\!\left(\sqrt{\frac n{\log n}}\right). \tag{4}

Here a clique colouring has no monochromatic inclusion-wise maximal clique of size at least two.

The deduction needed for Problem #620 is short and is checked here, rather than merely quoted. Let $G$ be $K_4$-free and take such a clique colouring with $q=O(\sqrt{n/\log n})$ colours. If one colour class contained a triangle $T$, then $T$ would be a maximal clique: a vertex extending it would form a $K_4$. That would be a forbidden monochromatic maximal clique. Hence every colour class is triangle-free. The largest class has size at least

\frac nq=\Omega(\sqrt{n\log n}). \tag{5}

This reduction is (a), with (4) as the explicitly named (b) input. It is stronger than the lower bound displayed on the live page.

Combining (3) and (5), there are absolute $c,C',N>0$ such that for every $n\ge N$,

c\sqrt{n\log n}\le f(n)\le C'\sqrt{n\log n}. \tag{6}

Thus (subject to the correctness of arXiv:2607.16118v1) the asymptotic order asked for on the live page is now determined.

2.4 Structural audit of the new upper construction

The hard probability estimates were not replaced by handwaving. The exact dependency is isolated.

The preprint takes the union of two independently random collections of blown-up balanced $s$-partite graphs. It first deletes any edge whose endpoints occur together in two blow-ups, so every surviving edge belongs to a unique blow-up. It then deletes an edge from every surviving triangle not contained in one blow-up.

(a) This deletion rule really makes the final graph $K_{s+1}$-free:

A putative $K_{s+1}$ contained in one blow-up is impossible because that

blow-up is $s$-partite.

Otherwise, take an edge $xy$ of the clique. It belongs to a unique

blow-up; choose another clique vertex $z$ outside that blow-up. The triangle $xyz$ was not contained in one blow-up, so the second deletion removed one of its edges, a contradiction.

The nontrivial statement that every $C(s)\sqrt{n\log n}$-set still contains $K_s$ is the content of the preprint's Lemmas 3.4 and 3.5, proved in its Sections 4 and 5. Theorem 3.1 then uses

\binom nk e^{-m/16}+o(1)=o(1),\qquad m=16k\log n;

indeed $\binom nk n^{-k}\le 1/k!\to0$. Those two lemmas, not the elementary specialisation or a missing all-$n$ step, are exactly what remains if one declines to accept the named preprint theorem.

No later primary source, correction, or version was found in searches through 2026-07-28. That is a bibliographic search result, not a claim that no unindexed discussion exists.

3. Independent exact small cases

The standalone verifier is erdos620_wavew003_verify.py.

3.1 Exhaustive method

(d) For each $1\le n\le10$, the checker invokes Brendan McKay's nauty-geng -k to generate one representative of every isomorphism class of $n$-vertex $K_4$-free graph. It does not trust the generated graph's invariant:

It decodes each graph6 record itself.
It reconstructs adjacency bitsets and directly rejects any graph

containing a $K_4$.

It records the triangle hypergraph $\mathcal T(G)$.
It uses the exact equivalence

\[ G[V\setminus D]\text{ is triangle-free} \quad\Longleftrightarrow\quad D\text{ meets every member of }\mathcal T(G). \tag{7} \] Exhausting deletion sets therefore computes $\alpha_3(G)$.

A final exact subset scan independently rechecks each reported witness.

Because (1) is invariant under isomorphism, one graph per isomorphism class is enough. Completeness through $n=10$ is delegated only to the standard geng canonical generator.

As an independent overlap check, the same Python file also enumerates all labelled graphs directly, with no nauty involvement, through $n=7$. The numbers of labelled $K_4$-free graphs obtained were

1,\ 2,\ 8,\ 63,\ 958,\ 27626,\ 1486597,

and the resulting $f(n)$ values agree with the isomorphism-class sweep.

3.2 Verified table and certificates

The exact computational table is:

| $n$ | $f(n)$ | unlabelled $K_4$-free classes checked | witness (graph6) | |---:|---:|---:|:---| | 1 | 1 | 1 | @ | | 2 | 2 | 2 | A_ | | 3 | 2 | 4 | Bw | | 4 | 3 | 10 | C} | | 5 | 4 | 29 | Dvw | | 6 | 4 | 120 | E]~o | | 7 | 4 | 685 | FUzro | | 8 | 5 | 6,431 | GCQurW | | 9 | 5 | 103,164 | HEhuTxm | | 10 | 6 | 2,894,632 | I?bFUYuVg |

Thus

(f(1),\ldots,f(10))=(1,2,2,3,4,4,4,5,5,6). \tag{8}

The witnesses for $n\le6$ are balanced complete tripartite graphs. The first departure is informative: FUzro is $\overline{C_7}$.

(a) Its certificate can also be checked by hand. A $K_4$ in $\overline{C_7}$ would be an independent 4-set in $C_7$, impossible. Every five vertices induce a proper subgraph of $C_7$, hence a union of paths, and have an independent 3-set; therefore every five vertices of the complement contain a triangle. Four consecutive cycle vertices induce a $P_4$, whose complement is triangle-free. Hence $\alpha_3(\overline{C_7})=4$.

The three larger graph6 certificates were decoded and recomputed as follows:

| graph6 | vertices | edges | triangles | $K_4$'s | $\alpha_3$ | |:---|---:|---:|---:|---:|---:| | GCQurW | 8 | 13 | 5 | 0 | 5 | | HEhuTxm | 9 | 20 | 12 | 0 | 5 | | I?bFUYuVg | 10 | 22 | 13 | 0 | 6 |

For complete transparency, the $n=10$ witness has edge set

\begin{split} \{&04,05,06,07,08,\ 15,16,17,19,\ 26,28,\ 38,39,\\ &46,47,49,\ 57,58,59,\ 68,69,\ 89\}, \end{split}

where $ij$ denotes $\{i,j\}$. The verifier checks all $\binom{10}{7}=120$ seven-sets contain a triangle. The set $\{0,1,2,3,4,5\}$ is triangle-free (its only induced edges are $04,05,15$), and the exact subset scan checks this lower certificate as well.

3.3 Reproduction and measured cost

The explicit witnesses require no external generator:

python3 runs/erdos620_wavew003_verify.py --certificates-only

This printed:

graph6=FUzro       n=7   edges=14  triangles=7   K4=no  alpha3=4
graph6=GCQurW      n=8   edges=13  triangles=5   K4=no  alpha3=5
graph6=HEhuTxm     n=9   edges=20  triangles=12  K4=no  alpha3=5
graph6=I?bFUYuVg   n=10  edges=22  triangles=13  K4=no  alpha3=6
Euler-transform check: unlabelled_K4_free(n=11)=138892304
ALL CERTIFICATE CHECKS PASSED

The independent labelled cross-check is:

python3 runs/erdos620_wavew003_verify.py --labelled-max 7 --max-n 7

It checked all $2^{21}=2,097,152$ labelled graphs at $n=7$, found 1,486,597 of them $K_4$-free, and completed in 17.4 seconds wall time.

The full sweep is:

python3 runs/erdos620_wavew003_verify.py --max-n 10

It checked 2,894,632 isomorphism classes at $n=10$, printed (8), and ended ALL CHECKS PASSED. The final measured full-run wall time was 76.6 seconds, 78.7 CPU-seconds, with 15.8 MB maximum resident memory.

The next brute-force step was deliberately not run. OEIS A079574's connected $K_4$-free counts give, by the Euler transform, 138,892,304 unlabelled $K_4$-free graphs at $n=11$. At the measured invariant-checking rate, the same method would take approximately

\frac{138892304}{2894632}\,(74.3\text{ s})\approx3600\text{ CPU-s},

about one core-hour rather than a few CPU-minutes. A realistic commodity cloud cost is roughly USD 0.05--0.20 for that CPU time, but the relevant constraint here is the requested local runtime cap. A SAT formulation or a property-directed nauty filter would be the appropriate next computation.

4. What is and is not established

(b) The uniform asymptotic answer is

$f(n)=\Theta(\sqrt{n\log n})$, conditional only on the named upper-bound theorem in the very recent arXiv v1 preprint. The lower-bound source is peer-reviewed, and its application was checked directly.

(a) There is no subsequence/finiteness gap: the quantitative upper

theorem is explicitly for every $n\ge s^C$, and the lower reduction is for every sufficiently large $n$.

(d) Equation (8) is an exact finite computation. Through $n=7$, two

independent completeness routes agree; through $n=10$, completeness is modulo nauty-geng, while every graph invariant and every certificate is recomputed from scratch.

I make no claim that the small table is bibliographically novel. The

valuable current-state finding is that the live OPEN page has not yet incorporated arXiv:2607.16118v1.

PROVED: (b) Morris--Sahasrabudhe--Verstraëte, arXiv:2607.16118v1, gives the uniform answer $f(n)=\Theta(\sqrt{n\log n})$; independently (d), exhaustive checks give $f(1),\ldots,f(10)=1,2,2,3,4,4,4,5,5,6$.

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