ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1013 · PARTIAL

Erdős problem #1013 — wave w028

Date of live-page and literature audit: 2026-07-29 UTC.

Claim labels used throughout:

0. Mandatory live-page gate

(d) I fetched both the live problem page and its discussion thread through the Bright Data browser path:

The page was last edited 21 January 2026. It says OPEN, 0 claimed proofs, “Currently working on this problem: None”, and “Interested in collaborating: None”. Thus the requested stop condition is not triggered.

Verbatim live statement

Let \(h_3(k)\) be the minimal \(n\) such that there exists a triangle-free graph on \(n\) vertices with chromatic number \(k\). Find an asymptotic for \(h_3(k)\), and also prove \[ > \lim_{k\to\infty}\frac{h_3(k+1)}{h_3(k)}=1. > \]

Results and discussion actually listed on the live page

(d) The page states that \(h_3\) is dual to the function \(f(n)\) of problem #1104, where \(f(n)\) is the largest chromatic number of an \(n\)-vertex triangle-free graph. It lists:

\[ h_3(k)\gg \frac{\log k}{\log\log k}k^2 \]

as a result of Graver and Yackel, and it displays

\[ \left(\frac12-o(1)\right)k^2\log k \le h_3(k)\le (1+o(1))k^2\log k \tag{live-page display} \]

as an implication of the bounds for \(f\) on problem #1104. It points to problem #920 for the \(K_r\)-free generalization.

(d) There are 15 comments. Their mathematically relevant content is:

No comment claims a solution, and no user is marked as currently working.

1. Primary-source audit

(d) Erdős's original item is problem 6 in Some unsolved problems in graph theory and combinatorial analysis (1971), pp. 98–99. With his notation \(g(3,n)\), he asks for an asymptotic and separately asks whether \(g(3,n+1)/g(3,n)\to1\). The scan is at <https://www.renyi.hu/~p_erdos/1971-25.pdf>.

(d) The Graver–Yackel paper exists as J. Combinatorial Theory 4 (1968), 125–175, DOI <https://doi.org/10.1016/S0021-9800(68)80038-9>. This verifies the bibliographic identity of the live-page citation. Its full text was not openly retrievable through the DOI, CORE mirror, or Elsevier text-mining endpoint on this VM, so I do not invent a theorem number or claim direct inspection of its asymptotic proof; the bound recorded in Section 0 is taken from the authoritative live page as instructed.

(b) Davies and Illingworth, The \(\chi\)-Ramsey problem for triangle-free graphs, Theorem 1, prove

\[ f(n)\le (2+o(1))\sqrt{\frac n{\log n}}. \]

Primary sources: <https://arxiv.org/abs/2107.12288> and DOI <https://doi.org/10.1137/21M1437573>.

(b) Hefty, Horn, King, and Pfender prove

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

The paper is Improving \(R(3,k)\) in just two bites, arXiv:2510.19718v3, last revised 19 February 2026: <https://arxiv.org/abs/2510.19718>. As derived below, this gives

\[ f(n)\ge (1-o(1))\sqrt{\frac n{\log n}}. \]

(b) Goedgebeur proves \(32\le h_3(6)\le40\), \(h_3(7)\ge41\), and, more specifically, that a hypothetical triangle-free \(6\)-chromatic graph on 32 vertices must have maximum degree 6, while one on 33 vertices must have maximum degree 6 or 7. See Theorem 2, Corollary 3, and Claim 8 of On minimal triangle-free 6-chromatic graphs, arXiv:1707.07581, DOI 10.1002/jgt.22467: <https://arxiv.org/abs/1707.07581>.

(b) Abrishami and Erfanian prove Reed's conjectured bound

\[ \chi(G)\le \left\lceil\frac{\Delta(G)+\omega(G)+1}{2}\right\rceil \]

for every triangle-free graph of order at most 32 whose chromatic number is not 5 (their Theorem 3). They also prove it for every maximal triangle-free graph of maximum degree less than 7 (their Theorem 4). See A note on Reed's conjecture for triangle-free graphs, Discrete Mathematics 346 (2023), 113609, DOI <https://doi.org/10.1016/j.disc.2023.113609>.

(d) Searches by the exact \(h_3(k)\) notation, by the title/phrasing of the problem, and through the papers above found no primary source claiming the asymptotic constant or the consecutive-ratio limit. This is a literature-search miss, not a proof of nonexistence.

2. Exact inversion lemma and a factor-of-two problem in the live-page bound

Let

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

and let \(h(k)=h_3(k)\).

2.1 Exact threshold relation

(a) Adding isolated vertices shows that \(f\) is nondecreasing. If \(G\) has \(n+1\) vertices and chromatic number \(r\), deleting any vertex leaves chromatic number at least \(r-1\); hence

\[ f(n+1)\le f(n)+1. \]

(a) If \(f(n)\ge k\), take a witnessing graph and delete vertices one at a time. Chromatic number changes by at most one per deletion, so an induced subgraph of chromatic number exactly \(k\) appears. Conversely, a graph counted by \(h(k)\) witnesses \(f(h(k))\ge k\). Therefore

\[ h(k)=\min\{n:f(n)\ge k\}. \tag{1} \]

At this first threshold, the one-step inequality also gives \(f(h(k))=k\).

2.2 Transfer of leading constants

(a) Proposition. Suppose \(0<A\le B\) and

\[ (A-o(1))\sqrt{\frac n{\log n}} \le f(n)\le (B+o(1))\sqrt{\frac n{\log n}}. \tag{2} \]

Then

\[ \left(\frac{2}{B^2}-o(1)\right)k^2\log k \le h(k)\le \left(\frac{2}{A^2}+o(1)\right)k^2\log k. \tag{3} \]

(a) Proof. Equation (2) first gives the coarse estimate \(h(k)=\Theta(k^2\log k)\), so

\[ \log h(k)=(2+o(1))\log k. \tag{4} \]

For a fixed \(C>2/A^2\), put \(n=Ck^2\log k\). Then

\[ (A-o(1))\sqrt{\frac n{\log n}} =(A-o(1))\sqrt{\frac C2}\,k>k, \]

so (1) gives \(h(k)\le n\). Let \(C\downarrow2/A^2\). The lower bound is identical: for fixed \(c<2/B^2\), monotonicity and the upper half of (2) give

\[ f(\lfloor ck^2\log k\rfloor) \le(B+o(1))\sqrt{\frac c2}\,k<k, \]

so \(h(k)>\lfloor ck^2\log k\rfloor\). Let \(c\uparrow2/B^2\). ∎

2.3 Applying the verified current \(f\)-bounds

(b) The cited #1104 bounds have \(A=1\) and \(B=2\). Proposition (3) therefore gives

\[ \boxed{ \left(\frac12-o(1)\right)k^2\log k \le h_3(k)\le (2+o(1))k^2\log k.} \tag{5} \]

It does not give upper coefficient \(1\).

(a) The Ramsey calculation independently gives the same answer. More generally, a construction

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

provides a triangle-free graph with \(N=(c+o(1))t^2/\log t\) and \(\alpha<t\). Thus

\[ \chi\ge \frac N{t-1}=(c+o(1))\frac t{\log t} =(\sqrt{2c}+o(1))\sqrt{\frac N{\log N}}. \]

Inverting gives \(h(k)\le(1/c+o(1))k^2\log k\). HHKP has \(c=1/2\), hence coefficient \(2\), not \(1\).

(a) An upper coefficient \(1\) for \(h_3\) would require a currently unverified construction with

\[ f(n)\ge(\sqrt2-o(1))\sqrt{\frac n{\log n}}, \tag{6} \]

or, if one insists on deriving it only from independence number/Ramsey graphs, the much stronger coefficient \(c=1\) in the lower bound for \(R(3,t)\).

(d) The live page's coefficient \(1\) is faithfully recorded in Section 0, but it is not supported by the cited #1104 inequalities. I found no separate primary source for (6). Consequently I treat (5), not the live-page upper coefficient, as the source-verified interval. It remains logically possible that an uncited construction proves the stronger bound.

(c) The most likely explanation is a dropped factor \(2\) when replacing \(\log h(k)\) by \(2\log k\), but this diagnosis is not independently documented.

3. A sharper concrete finite bound: \(33\le h_3(6)\le40\)

(b) Proposition.

\[ \boxed{33\le h_3(6)\le40.} \tag{7} \]

(b) Proof. Goedgebeur proves \(h_3(6)\ge32\), and his Claim 8 says that a hypothetical \((6,32)\)-graph \(G\) has \(\Delta(G)=6\). Since \(G\) is triangle-free and \(6\)-chromatic, \(\omega(G)=2\). Abrishami–Erfanian's order-32 theorem applies because \(\chi(G)=6\ne5\), and gives

\[ 6=\chi(G) \le\left\lceil\frac{6+2+1}{2}\right\rceil =5, \]

a contradiction. Hence no \((6,32)\)-graph exists and \(h_3(6)\ge33\). Goedgebeur's explicit \((6,40)\)-graphs give the upper bound. ∎

(d) I do not claim priority for this immediate two-paper corollary. The secondary OEIS entry A292528, even though it was modified on 27 July 2026, still records only \(32\le h_3(6)\le40\); that is evidence that the corollary is at least easy to overlook, not evidence of novelty.

(d) The verifier decodes from scratch the graph6 witness printed in the commented appendix of arXiv:1707.07581v3. It checks 40 vertices, 213 edges, no triangle, independently finds and checks a 6-coloring, and builds the ordinary 5-coloring CNF. CaDiCaL 1.9.5 and Glucose 4.2 independently return UNSAT, so the run fully rechecks that this explicit graph is 6-chromatic. This remains computational-only because no separately checked DRAT proof is emitted.

The explicit graph6 construction is:

g???A???T_GtIGFo?@G?I?DO?V?AOW@OWEQPBAD?EDOFaAXocgso_iDS?gVBX_cOoGALAx_k_ACs_@GaHA?sGgSJ@_OILChoGEQSAqSGDCFO@?q_wGOm?P~qEW??F|@w???

For the fixed graph, the coloring CNF uses variables \(y_{v,c}\), an exactly-one-color constraint for each vertex, and

for u, v in edges:
    for color in range(q):
        clauses.append([-y[u, color], -y[v, color]])

It canonically orders colors by first occurrence to remove color-permutation symmetry. Every coloring can be relabeled this way, so the symmetry break preserves satisfiability. The \(q=5\) instance has 200 variables and 1,665 clauses.

3.1 Exact reduction of the next finite case

(b) If \(h_3(6)=33\), then there must exist a maximal triangle-free \(6\)-chromatic graph \(H\) with

\[ |V(H)|=33,\qquad \Delta(H)=7. \tag{8} \]

Indeed, saturate a hypothetical 33-vertex example by adding edges while preserving triangle-freeness. Its chromatic number stays 6: if it rose to at least 7, vertex deletion would expose an induced subgraph of chromatic number exactly 7 on at most 33 vertices, contradicting Goedgebeur's \(h_3(7)\ge41\). Claim 8 gives \(\Delta(H)\in\{6,7\}\). If \(\Delta(H)=6\), Abrishami–Erfanian's theorem for maximal triangle-free graphs of maximum degree less than 7 would give Reed's bound \(\chi(H)\le5\), a contradiction. This proves (8).

(b) Since the lower bound \(h_3(6)\ge33\) makes \(H\) minimum-order and hence vertex-critical, for a degree-7 vertex \(v\),

\[ J=H-N[v] \]

is a triangle-free \(5\)-chromatic graph on 25 vertices. To see the chromatic assertion directly, \(J\subset H-v\) gives \(\chi(J)\le5\); if \(J\) were 4-colorable, color the independent set \(N(v)\) with a fifth color and give \(v\) one of the first four colors, contradicting \(\chi(H)=6\). Moreover, maximal triangle-freeness means every vertex outside \(N[v]\) has a neighbor in \(N(v)\); hence it loses at least one incident edge upon passing to \(J\), and \(\Delta(J)\le6\). Thus

\[ \boxed{h_3(6)=33\ \Longrightarrow\ \text{a triangle-free }(5,25,\le6)\text{-graph exists}.} \tag{9} \]

This is only a necessary condition, not an existence claim. Reed's bound permits equality here: \(\lceil(6+2+1)/2\rceil=5\). The exact finite obstruction remaining at order 33 is therefore no longer an arbitrary graph search; it is the extension problem from these constrained 25-vertex remainders.

4. Exact small-case recomputation

(d) The standalone checker rebuilds a SAT instance from the definitions. For every possible edge \(ij\) it has a Boolean variable \(x_{ij}\).

\[ \neg x_{ij}\vee\neg x_{i\ell}\vee\neg x_{j\ell}, \] which is exactly triangle-freeness.

The core generator is:

for i, j, k in combinations(range(n), 3):
    clauses.append([-x[i, j], -x[i, k], -x[j, k]])

for coloring in canonical_partitions(n, q):
    clauses.append([
        x[i, j] for i, j in combinations(range(n), 2)
        if coloring[i] == coloring[j]
    ])

clauses.append([x[0, 1]])

(d) For \(n=10,q=3\), this has 45 variables, 120 triangle clauses, 9,842 coloring-partition clauses, and one symmetry clause: 9,963 clauses total. CaDiCaL 1.9.5 and Glucose 4.2 independently return UNSAT (280,389 and 277,097 conflicts, respectively). If a smaller counterexample existed, adding isolated vertices would produce one on exactly 10 vertices. The checker separately constructs the 11-vertex Mycielski graph of \(C_5\), checks triangle-freeness, proves by exact DSATUR backtracking that it is not 3-colorable, and exhibits a 4-coloring.

(d) The analogous \(n=4,q=2\) computation plus the explicit \(C_5\) recomputes:

\[ h_3(1),h_3(2),h_3(3),h_3(4)=1,2,5,11. \]

These are computational-only claims in this report because the run does not emit a formally checked DRAT certificate. They agree with the classical exact theorems. Jensen and Royle's exhaustive result gives \(h_3(5)=22\) (DOI <https://doi.org/10.1002/jgt.3190190111>).

Combining the literature and this run gives the current finite summary

| \(k\) | \(h_3(k)\) | status in this report | |---:|---:|---| | 1 | 1 | (a) | | 2 | 2 | (a) | | 3 | 5 | (d) recomputed; classical elementary proof | | 4 | 11 | (d) recomputed; classical Chvátal theorem | | 5 | 22 | (b) Jensen–Royle | | 6 | \(33\) to \(40\) | (b) Proposition (7) |

5. Why the consecutive-ratio question still does not follow

(a) Since \(h(k)\) is increasing,

\[ \frac{h(k+1)}{h(k)}\to1 \quad\Longleftrightarrow\quad h(k+1)-h(k)=o(h(k)). \tag{10} \]

More exactly, (1) and the fact that \(f\) increases by at most one give

\[ h(k+1)-h(k)=\bigl|\{n:f(n)=k\}\bigr|. \tag{11} \]

Thus the ratio question is precisely the assertion that every level-set plateau of \(f\) has length \(o(h(k))\). The global constant-factor bounds do not control this local plateau length. From the source-verified interval (5) they give only

\[ 1\le\liminf_k\frac{h(k+1)}{h(k)} \le\limsup_k\frac{h(k+1)}{h(k)}\le4. \]

Even accepting the live page's unsupported upper coefficient \(1\) would improve the last number only to \(2\), not to \(1\).

(a) A minimum-order \((k+1)\)-chromatic graph is vertex-critical. For every vertex \(v\) in such a triangle-free graph \(G\),

\[ \chi(G-N[v])=k. \]

Indeed, \(G-N[v]\) has chromatic number at most \(k\) because it lies in \(G-v\). If it were \((k-1)\)-colorable, color the independent set \(N(v)\) with one new color and color \(v\) with one of the first \(k-1\) colors, producing a \(k\)-coloring of \(G\). Therefore

\[ h(k+1)-h(k)\ge d(v)+1. \tag{12} \]

This standard critical-neighborhood mechanism bounds the gap in the wrong direction for (10).

(a) Mycielski's construction gives

\[ h(k+1)\le2h(k)+1, \]

again a factor-two statement rather than an asymptotically lossless lift.

(c) Exact missing lemma. A direct route to the ratio limit would be an asymptotically lossless chromatic lift:

For every \(\varepsilon>0\), for all sufficiently large \(k\), some minimum-order triangle-free \(k\)-chromatic graph can be converted into a triangle-free \((k+1)\)-chromatic graph on at most \((1+\varepsilon)h(k)\) vertices.

This lemma is precisely strong enough to give (10). I found no such operation in the primary literature. Mycielski duplication, critical-neighborhood deletion, and global Ramsey constructions each fail to supply it for the reasons above.

(a), conditional on the displayed hypothesis. An exact asymptotic

\[ f(n)\sim A\sqrt{\frac n{\log n}} \]

would also settle both requests at once: Proposition (3) would give

\[ h(k)\sim\frac{2}{A^2}k^2\log k, \]

whose consecutive ratio is 1. Present methods do not determine \(A\).

6. Computation wall and cost

(a) Applying the explicit “one clause per coloring partition” SAT formulation to the necessary \((5,25,\le6)\) remainder in (9) would require

\[ \sum_{j=1}^{4}S(25,j) =46\,912\,504\,507\,051 \]

coloring-blocking clauses, before degree, criticality, or extension constraints. Even at an unrealistically favorable sustained generation rate of \(10^8\) clauses per second, merely streaming them would cost about 130 core-hours. The verifier recomputes the Stirling-number total.

(a) The still less structured direct formulation on 33 vertices would require

\[ \sum_{j=1}^{5}S(33,j) =970\,128\,145\,147\,602\,322\,502 \]

clauses, or \(2.695\times10^9\) core-hours (about \(3.08\times10^5\) core-years) at the same rate. Neither formulation was run. A serious attack on order 33 would need specialized maximal-triangle-free/critical-graph generation or a lazy SAT/QBF scheme. Goedgebeur already reports that the related \((5,25,5)\)-graph generation was infeasible for his 2017 methods. Without implementing and benchmarking such a generator, a smaller core-hour estimate would be invented rather than evidence-based.

7. Reproduction

The full, standalone source is:

runs/erdos1013_wavew028_reverify.py

Run:

/home/exedev/.venv/bin/python runs/erdos1013_wavew028_reverify.py

(d) On this VM the complete run takes about 27 seconds. It recomputes the constant conversion numerically in log-space, the order-32 Reed arithmetic, the order-33 remainder and both naive costs, both small graph-existence UNSAT results with two solvers, the \(C_5\) and Grötzsch witnesses, and the complete 6-chromatic check of Goedgebeur's 40-vertex witness. The observed final line is ALL CHECKS PASSED.

PARTIAL: proved the cited f-bounds invert to coefficients 1/2 and 2 (exposing an unsupported factor-two live-page bound), derived 33 <= h_3(6) <= 40 with an explicit fully rechecked upper witness, and reduced the order-33 and ratio questions to precise finite and plateau obstructions.

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