ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1011 · PARTIAL

Erdős problem #1011 — wave w028

Date: 2026-07-29 UTC

Claim labels

Step 0: authoritative live page

[d] Page observation. I fetched <https://www.erdosproblems.com/1011> through the Bright Data browser path on 2026-07-29, then separately fetched its discussion thread at <https://www.erdosproblems.com/forum/discuss/1011>. This was a real browser load, not a cached tracker record. The page said:

Thus no skip condition applied.

Verbatim live statement

Let \(f_r(n)\) be minimal such that every graph on \(n\) vertices with \(\geq f_r(n)\) edges and chromatic number \(\geq r\) contains a triangle. Determine \(f_r(n)\).

The page identifies the original source as P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, pp. 97–109 (1971), MR 0277392.

Results listed on the page

The following are transcribed mathematically from the live page.

\[ f_2(n)=\left\lfloor\frac{n^2}{4}\right\rfloor+1. \]

\[ f_3(n)=\left\lfloor\frac{(n-1)^2}{4}\right\rfloor+2. \]

\[ f_r(n)=\frac{n^2}{4}-\frac{g(r)}2n+O(1), \] where \(g(r)\) is the largest \(m\) such that every triangle-free graph of chromatic number at least \(r\) requires deletion of at least \(m\) vertices to become bipartite.

\[ \frac{\log r}{\log\log r}r^2\ll g(r)\ll(\log r)^2r^2. \]

\[ (1/2-o(1))r^2\log r\le g(r)\le(2+o(1))r^2\log r, \] attributing the lower bound to Davies–Illingworth and the upper bound to Hefty–Horn–King–Pfender.

\[ f_4(n)=\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+6. \]

All nine comments read

[d] Page observation. The site warns that comments are user-provided and unverified. Their mathematical content, in compact chronological/topic form, is:

  1. M. Sellke points to Simonovits, Theorem 2.7, and to the Ren–Wang–Wang–Yang \(r=4\) preprint.
  2. Z. Hunter relates an upper bound for \(g(r)\) to the new Ramsey construction.
  3. T. Bloom asks whether the resulting leading constant is \(2\).
  4. Hunter initially computes a ratio with constant \(1\).
  5. Hunter relates the other direction to the minimum order of a triangle-free graph of chromatic number \(r-2\), citing Davies–Illingworth.
  6. W. Cames van Batenburg corrects the logarithmic conversion and obtains constants \(1/2\) and \(2\).
  7. Hunter acknowledges that \(\log(r^2\log r)\sim2\log r\).
  8. Hunter also proposes

\[ g(r)\le\min\{R(3,k)-2k:R(3,k)/k>r-1\}, \] with a tentative constant-\(1\) consequence; the page body does not adopt that constant.

  1. Adenwalla notes a missing \(g(r)\) in a displayed inequality; the site says it was corrected.

No comment claims to solve the problem, and the separate proof-claims thread has count zero.

Primary-source audit

Original and classical sources

The \(g(r)\) constants

\[ \chi(H)\le(2+o(1))\sqrt{|V(H)|/\log |V(H)|} \] for triangle-free \(H\).

\(\chi(G)\le\chi(G[S])+2\). Hence \(\chi(G)\ge r\) implies \(\chi(G[S])\ge r-2\).

\[ g(r)\ge(1/2-o(1))r^2\log r. \]

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

\(N=(2+o(1))r^2\log r\) produces a triangle-free graph with chromatic number at least \(r\). The trivial deletion bound \(d_2(G)\le N\) then gives \[ g(r)\le(2+o(1))r^2\log r. \]

Thus the two constants printed on the live page are consistent with the checked primary theorems.

A live-page literature correction for \(r=4\)

[b] The current cited preprint is S. Ren, J. Wang, S. Wang, and W. Yang, Extremal triangle-free graphs with chromatic number at least four, arXiv:2404.07486v2, <https://arxiv.org/abs/2404.07486>. Version 2 was posted 19 October 2025. Its abstract and Theorem 1.4 say \(n\ge90\), not \(n\ge150\):

\[ e(G)\le\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+5 \quad(\chi(G)\ge4,\ G\text{ triangle-free},\ n\ge90), \]

with equality precisely for the stated Grötzsch blow-ups. Consequently,

\[ f_4(n)=\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+6 \qquad(n\ge90). \]

The live page's \(150\) is stale relative to the current version of its own cited source; this does not alter the page's OPEN status for the general problem.

Small-order literature

Exact reduction used in the computation

Define

\[ M_4(n)=\max\{e(G): |V(G)|=n,\ G\text{ triangle-free},\ \chi(G)\ge4\}. \]

[a] Whenever the set is nonempty,

\[ f_4(n)=M_4(n)+1. \]

Indeed, an extremal triangle-free graph shows that threshold \(M_4(n)\) is insufficient, while the definition of the maximum makes threshold \(M_4(n)+1\) sufficient.

[a] Connected-extremizer lemma. A graph attaining \(M_4(n)\) is connected. If a qualifying graph were disconnected, one component would have chromatic number at least four. Adding one edge from that component to another component creates no triangle, preserves chromatic number at least four, and increases the edge count. This justifies generating connected graphs only.

Explicit witnesses

For \(11\le n\le14\), define \(H_n\) as follows. Indices are modulo five.

\[ V(H_n)=\{u_0,\dots,u_4\}\cup\{v_0,\dots,v_4\}\cup W, \qquad |W|=n-10. \]

Its edges are

\[ u_i u_{i+1},\qquad v_i u_{i-1},\qquad v_i u_{i+1}, \qquad wv_i\quad(w\in W,\ 0\le i<5). \]

There are no other edges.

[a] Triangle-free. The \(u_i\) induce \(C_5\); the two \(u\)-neighbours of each \(v_i\) are nonadjacent; the \(v_i\) and \(W\) are each independent; and a vertex of \(W\) has no \(u\)-neighbour. These facts exclude every possible triangle.

[a] Chromatic number four. Choosing one \(w\in W\) gives the Mycielskian of \(C_5\) as an induced subgraph. For completeness, suppose it had a 3-colouring and rename the apex colour 3. Every \(v_i\) then has colour 1 or 2. Recolour every \(u_i\) of colour 3 with the colour of \(v_i\). Adjacent \(u\)'s remain differently coloured because \(v_i\) sees both neighbours of \(u_i\), producing an impossible 2-colouring of \(C_5\). Conversely, a 3-colouring of \(C_5\), copied from \(u_i\) to \(v_i\), plus a fourth colour on \(W\), is proper.

[a] Edge count.

\[ e(H_n)=5+10+5|W|=5n-35. \]

Thus the four witness edge counts are \(20,25,30,35\). For \(n=12,13,14\), this equals \(\lfloor(n-3)^2/4\rfloor+5\).

Exhaustive upper-bound computation

The standalone verifier is:

runs/erdos1011_wavew028_verify.py

SHA-256 before report creation:

e14e2302c89a345c3f6b3af5e49691dc06dfcbd748dc882ffe0dd99e76d854ce

It uses only Python's standard library and Debian nauty-geng 2.8.8. Run it from the repository root with:

python3 runs/erdos1011_wavew028_verify.py

For each \(n\), after checking \(H_n\) directly, it invokes the equivalent of

nauty-geng -q -ct n 'M_4_lower(n)+1:floor(n^2/4)'

The code then performs all of the following independently of geng:

  1. decodes each graph6 record with a from-scratch parser;
  2. recomputes its edge count two ways;
  3. checks connectivity and triangle-freeness by bitset adjacency;
  4. constructs a proper 3-colouring of every high-edge candidate;
  5. checks that colouring edge by edge;
  6. checks the witnesses with two separately written exact colouring searches;
  7. round-trips every labelled graph of order at most five through its graph6 encoder/decoder;
  8. checks all per-edge class counts against the recorded census.

The important point is that the candidate upper bounds do not depend on trusting an UNSAT answer from the colouring routine: every generated high-edge graph comes with an actual 3-colouring, and the verifier checks that certificate. The only non-local dependency is nauty-geng's documented completeness—one representative of every unlabelled connected triangle-free graph in the requested edge range.

Census

[d] The full run checked 109,782 high-edge isomorphism classes:

| \(n\) | witness \(e(H_n)\) | generated range | classes checked | conclusion | |---:|---:|---:|---:|---:| | 11 | 20 | 21–30 | 2,725 | \(M_4(11)=20\) | | 12 | 25 | 26–36 | 5,476 | \(M_4(12)=25\) | | 13 | 30 | 31–42 | 16,613 | \(M_4(13)=30\) | | 14 | 35 | 36–49 | 84,968 | \(M_4(14)=35\) |

The exact per-edge histograms were:

n=11: {21:1550, 22:691, 23:279, 24:122, 25:49,
       26:21, 27:7, 28:4, 29:1, 30:1}
n=12: {26:3187, 27:1340, 28:553, 29:229, 30:96, 31:41,
       32:17, 33:7, 34:3, 35:2, 36:1}
n=13: {31:9788, 32:4062, 33:1632, 34:672, 35:267, 36:117,
       37:43, 38:19, 39:7, 40:4, 41:1, 42:1}
n=14: {36:50478, 37:20589, 38:8300, 39:3335, 40:1343,
       41:542, 42:222, 43:92, 44:37, 45:17, 46:7,
       47:3, 48:2, 49:1}

The observed full verification time was 43.56 seconds wall time and 55.27 CPU-seconds, with peak reported RSS 15,212 KiB.

Exact finite table

[d] Combining the checked witnesses and exhaustive upper bounds gives

\[ \boxed{f_4(11)=21,\quad f_4(12)=26,\quad f_4(13)=31,\quad f_4(14)=36.} \]

For \(n=12,13,14\), this is exactly

\[ f_4(n)=\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+6. \]

At \(n=11\), the value is 21, one below the large-\(n\) expression 22.

Witness graph6 strings, also regenerated and decoded by the verifier, are:

n=11  JhdLA_gc?N_
n=12  KhdLA_gc?N_}
n=13  LhdLA_gc?N_}@{
n=14  MhdLA_gc?N_}@{@{?

What remains and the precise wall

\[ e(G)\le\left\lfloor\frac{(n-3)^2}{4}\right\rfloor+5 \quad\text{for every triangle-free }G,\ \chi(G)\ge4,\ 15\le n\le89. \] Proving this uniformly would close the \(r=4\) gap.

PARTIAL: [d] Exhaustive generation plus independently validated colouring certificates give \(f_4(11)=21\), \(f_4(12)=26\), \(f_4(13)=31\), and \(f_4(14)=36\); the general problem remains open.

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