Erdős problem #1182 — wave6w report

Access/research date: 2026-07-27 UTC.

Result in one paragraph

The problem is still open, but two verifiable advances are available here. First, applying Sudakov's 2007 size-versus-Ramsey theorem to the live-page parameter gives

and hence \(f(n)=n^{3/2+o(1)}\). This improves the live page's displayed upper bound \(f(n)\ll n^{5/3}(\log n)^{2/3}\). This is (b), rigorous modulo Sudakov's named theorem. Second, a fresh finite census gives

The census regenerates all 853 connected unlabeled graphs on seven vertices and all 392 maximal triangle-free unlabeled graphs on thirteen vertices. It agrees with the published 1998 value but uses a new standalone checker here; this result is (d), computational-only, not asserted as a new non-computational theorem.

The complete verifier is runs/erdos1182_wave6w_reverify.py.

Claim labels

• (a) elementary-rigorous: proved directly in this report.
• (b) rigorous-modulo-named-theorem: the deduction is rigorous, conditional only on an explicitly named published theorem.
• (c) plausible/structural-unverified: useful structural evidence, not a proof.
• (d) computational-only: an exhaustive finite computation, with its dependencies and checks stated.

Step 0: mandatory live-page gate

I loaded the rendered live page and its discussion thread through the Bright Data browser path. Direct datacenter retrieval was not used as authority.

Verbatim current statement

The following is copied verbatim from the page's “View the LaTeX source” view:

Let $f(n)$ be maximal such that there is a connected graph $G$ with $n$ vertices and $f(n)$ edges such that\[R(K_3,G)= 2n-1.\]Let $F(n)$ be maximal such that every connected graph $G$ with $n$ vertices and $\leq F(n)$ edges has\[R(K_3,G)= 2n-1.\]Estimate $f(n)$ and $F(n)$. In particular, is it true that $F(n)/n\to \infty$?

Gate status

The rendered page said:

• OPEN;
• 0 claimed proofs for this problem;
• Currently working on this problem None;
• Interested in collaborating None;
• last edited 11 April 2026.

Thus the mandatory stop condition did not trigger.

All three live comments checked

The discussion thread contained exactly three comments:

1. At 21:08 on 14 March 2026, ebarschkis observed that Brandt's linear upper bound for the universal threshold answers the \(F(n)/n\to\infty\) subquestion negatively, supplied a reconstructed LaTeX/PDF, and later clarified that Brandt's \(f(n;3)\) is the live page's \(F(n)\). The page says it was updated to incorporate this.

2. At 22:32 on 14 March 2026, JakeMallen linked the archived .dvi and .ps files.

3. At 00:31 on 15 March 2026, ebarschkis noted OCR corruption in a PS-to-PDF conversion and the usefulness of a LaTeX rewrite for formalisation.

None is a claimed proof of the remaining estimation problem, and none identifies a current worker.

Known results listed on the live page

The live page records the following:

• \(f(n)\geq F(n)\), and \(R(K_3,G)\geq 2n-1\) for connected \(n\)-vertex \(G\);
• Chvátal's \(R(K_3,T)=2n-1\) for every \(n\)-vertex tree \(T\);
• Burr–Erdős–Faudree–Rousseau–Schelp:

\[ \frac{17n+1}{15}\leq F(n) \leq \left(\frac{27}{4}+o(1)\right)n(\log n)^2, \]

with the lower bound for \(n\geq4\);

• Brandt's linear upper bound \(F(n)\leq84n\), resolving the displayed limit question negatively;
• Burr–Erdős–Faudree–Rousseau–Schelp:

\[ n^{3/2}(\log n)^{1/2}\ll f(n) \ll n^{5/3}(\log n)^{2/3}; \]

• for \(n=2,3,4,5,6\), respectively,

\[ F(n)=1,2,5,7,8,\qquad f(n)=1,2,5,8,12; \]

• the corresponding \(K_m\) generalisations and their displayed bounds.

Only these live-page statements and verified primary sources below were used as input facts.

Notation warning

The notation changes between sources:

| Meaning | Live page | BEFRS80 and BBH98 |

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

| every connected \(n\)-vertex graph with at most this many edges is \(K_3\)-good | \(F(n)\) | \(f(K_3,n)\), or \(f(n)\) in BEFRS80 |

| some connected \(n\)-vertex graph with this many edges is \(K_3\)-good | \(f(n)\) | \(g(K_3,n)\), or \(g(n)\) in BEFRS80 |

All formulas in the conclusions of this report use the live-page notation.

Primary-source literature audit

Sources actually opened

1. Erdős 1978. P. Erdős, “Problems and results in combinatorial analysis and combinatorial number theory,” Proceedings of the Ninth Southeastern Conference, pp. 29–40. The primary scan exists at Rényi Institute, file 1978-36.pdf; the relevant material is on printed page 33. This verifies that the problem and the two extremal quantities really occur in the cited original source.

2. BEFRS80. S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, “An extremal problem in generalized Ramsey theory,” Ars Combinatoria 10 (1980), 193–203. The primary author-archive PDF exists and contains the live page's low-order table and asymptotic theorems.

3. Brandt 1996. S. Brandt, “Expanding graphs and Ramsey numbers,” preprint A 96-24. The original Freie Universität Berlin PostScript exists. Its proof gives the eventual bound \(F(n)/n<84\). It also mentions that a different, refined analysis “not presented here” gives \(<11.75\); I do not use the unpresented refinement as a proved bound.

4. BBH98. S. Brandt, G. Brinkmann, and T. Harmuth, “All Ramsey numbers \(r(K_3,G)\) for connected graphs of order 9,” Electronic Journal of Combinatorics 5 (1998), #R7, DOI 10.37236/1345 and official PDF. Table 2 reports both extremal functions through \(n=12\). Section 4 explicitly asks for an independent computational check.

5. BGS12. G. Brinkmann, J. Goedgebeur, and J.-C. Schlage-Puchta, “Ramsey Numbers \(R(K_3,G)\) for Graphs of Order 10,” Electronic Journal of Combinatorics 19(4) (2012), #P36, DOI 10.37236/2548 and official PDF. It says that its new program independently confirmed every extremal value in BBH98 Table 2 but found no new \(F,f,h\) values.

6. Sudakov 2007. B. Sudakov, “Ramsey numbers and the size of graphs,” SIAM Journal on Discrete Mathematics 21 (2007), 980–986, DOI 10.1137/060667360, arXiv:0706.4102. Theorem 1.1 is the input to the improved upper bound below.

Targeted searches for the exact extremal-function notation, the titles above, and improvements to Sudakov's \(m^{2/3}/\log^{2/3}m\) bound did not locate a later primary source closing the logarithmic gap. That is an honest literature-search miss, not a proof that no such paper exists.

Published small values omitted from the live-page summary

BBH98 Table 2 gives the following. The \(n=2\) row is supplied by BEFRS80/the live page; the other rows are in BBH98. BGS12 later independently confirmed the BBH98 table.

| \(n\) | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

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

| live-page \(F(n)\) | 1 | 2 | 5 | 7 | 8 | 11 | 11 | 16 | 18 | 23 | 23 |

| live-page \(f(n)\) | 1 | 2 | 5 | 8 | 12 | 16 | 20 | 27 | 33 | 41 | 49 |

These are (d), published computer-assisted values. The present verifier independently recomputes only the \(n=7\) column.

A sharper asymptotic upper bound for the live-page \(f(n)\)

Sudakov's Theorem 1.1 with \(s=3\) says that there is an absolute \(c>0\) such that every graph \(G\) with \(m\) edges satisfies

This statement is for every graph \(G\), so in particular it applies to every connected \(n\)-vertex graph that contributes to the live-page \(f(n)\).

Let \(G\) attain \(m=f(n)\). By definition \(R(K_3,G)=2n-1<2n\). Combining this with (1),

and raising to the \(3/2\) power gives

Because \(G\) is a simple \(n\)-vertex graph, \(m\leq\binom n2 \[ \boxed{f(n)=O(n^{3/2}\log n).} \tag{3} \]

Every step after (1) is elementary. Thus (3) is (b), rigorous modulo Sudakov's Theorem 1.1.

Combining (3) with the BEFRS80 lower bound listed on the live page gives

and in particular

Equations (4)–(5) are (b), rigorous modulo BEFRS80 and Sudakov. I do not claim that this short deduction is novel; it is, however, a genuine improvement over the bound currently displayed on the live problem page.

For the universal threshold, the live-page BEFRS80 lower bound and Brandt upper bound already imply

which is (b), rigorous modulo those two named results. Determining the constants, a limit, or a sharper form remains open.

Elementary reduction used for the finite computation

Proposition

For a connected graph \(G\) on \(n\) vertices,

if and only if the complement of every edge-maximal triangle-free graph on \(2n-1\) vertices contains \(G\) as a not-necessarily-induced subgraph.

This proposition is (a), elementary-rigorous.

Proof

First, \(R(K_3,G)\geq2n-1\): on \(2n-2\) vertices, split the vertices into two sets of size \(n-1\), color every cross-edge red, and every within-part edge blue. The red graph is \(K_{n-1,n-1}\), hence triangle-free, while the blue graph is \(2K_{n-1}\), which contains no connected \(n\)-vertex graph.

Now consider a red/blue coloring on \(2n-1\) vertices with no red triangle. Its red graph \(X\) is triangle-free. Add red edges greedily while preserving triangle-freeness until obtaining an edge-maximal triangle-free graph \(T\) on the same vertex set. If \(\overline T\) contains \(G\), then the original blue graph \(\overline X\), which contains \(\overline T\), also contains \(G\). Conversely, if some maximal triangle-free \(T\) has \(G\nsubseteq\overline T\), then \(T,\overline T\) is a red/blue coloring of \(K_{2n-1}\) with neither a red \(K_3\) nor a blue \(G\). Together with the lower bound, this proves the equivalence. \(\square\)

Exact \(n=7\) computation

Enumeration

The standalone verifier runs:

python runs/erdos1182_wave6w_reverify.py

Its generation layer uses the installed nauty programs:

nauty-geng -q -c 7
nauty-geng -q -t -d1 13 | nauty-pickg -q -j1:

The first command gives one representative of each connected unlabeled graph on seven vertices. For a triangle-free graph, edge-maximality is equivalent to every nonadjacent pair having at least one common neighbor; this is exactly the pickg -j1: condition. A maximal triangle-free graph of order greater than one cannot have an isolated vertex, which justifies -d1.

The script independently reparses graph6, checks all generated seven-vertex graphs for connectivity, and checks all generated thirteen-vertex graphs for triangle-freeness and the common-neighbor maximality condition. It then uses its own bitset backtracker—not a nauty embedding routine—to test whether each pattern is a non-induced subgraph of each complement. Every positive result is rechecked directly as an injective edge-preserving map.

The enumeration/completeness and isomorph rejection rely on nauty. Consequently this section is (d), computational-only.

Full census

Here “good” means \(R(K_3,G)=13\), by the elementary proposition.

| edges | connected graphs | good | bad |

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

| 6 | 11 | 11 | 0 |

| 7 | 33 | 33 | 0 |

| 8 | 67 | 67 | 0 |

| 9 | 107 | 107 | 0 |

| 10 | 132 | 132 | 0 |

| 11 | 138 | 138 | 0 |

| 12 | 126 | 123 | 3 |

| 13 | 95 | 88 | 7 |

| 14 | 64 | 51 | 13 |

| 15 | 40 | 19 | 21 |

| 16 | 21 | 3 | 18 |

| 17 | 10 | 0 | 10 |

| 18 | 5 | 0 | 5 |

| 19 | 2 | 0 | 2 |

| 20 | 1 | 0 | 1 |

| 21 | 1 | 0 | 1 |

| total | 853 | 772 | 81 |

There are no bad graphs through 11 edges, there are bad graphs with 12 edges, there are good graphs with 16 edges, and there are no good graphs with 17 or more edges. Therefore

This conclusion is (d), computational-only. The total of 772 good graphs also independently matches the \(n=7,\ R(K_3,G)=13\) entry in BBH98 Table 1.

Explicit first bad graph

One 12-edge bad graph \(B\) is \(K_5\) with two pendant vertices, both attached to the same vertex of the \(K_5\). Its graph6 code in the generated labeling is

FCe^w

An explicit red witness on \(\mathbb Z/13\mathbb Z\) is

This \(T\) is 4-regular with 26 edges. The verifier checks directly that it is triangle-free and checks all \(\binom{13}{5}=1287\) five-subsets to establish \(\alpha(T)\leq4\). Hence \(\overline T\) has no \(K_5\), and therefore has no copy of \(B\). This is an explicit finite coloring showing \(R(K_3,B)>13\). Its graph6 code is

LhEIHEPQHGaPaP

The construction formula is explicit; the finite triangle/independence checks are (d), computational-only in this report.

Explicit maximum-edge good graph

One 16-edge good graph is

with graph6 code

FQ~vw

The verifier finds and directly validates a copy of \(Q\) in the complement of every one of the 392 maximal triangle-free thirteen-vertex graphs. Thus \(Q\) is good by the elementary reduction. This is (d), computational-only.

Reproducibility and cross-checks

The completed packaged run reported:

connected unlabeled graphs on 7 vertices: 853
maximal triangle-free unlabeled graphs on 13 vertices: 392
embedding searches: 330810
directly rechecked positive certificates: 330729
total good: 772
total bad: 81
F(7) = 11
f(7) = 16
VERIFIED: connected7=853 mtf13=392 good=772 bad=81 F7=11 f7=16

A final quiet rerun after adding the explicit \(C_4\dot\cup K_2\dot\cup K_1\) component check used 76.80 user-CPU seconds, 63.44 wall seconds, and 16,384 KiB maximum RSS. python -m py_compile and git diff --check both passed. The verifier's SHA-256 was:

7b4c60f65e7e3e972865878bcadd16f27e7c92d49eb2bf17cc82701680d12c5a

Before packaging, I also classified all 853 graphs using NetworkX's independent VF2 monomorphism implementation. It produced the identical edge-by-edge census, \(772/81\) split, \(F(7)=11\), and \(f(7)=16\), in 144.95 wall seconds. The two embedding implementations share the same nauty-generated graph lists, so this cross-check does not independently certify nauty's completeness; it does independently check the custom embedding search. All of these statements are (d), computational-only.

Exact remaining wall

Asymptotics

The strongest conclusion obtained here for the existential extremum is the factor-\(\sqrt{\log n}\) interval in (4). Sudakov explicitly conjectures the stronger universal size bound

for every \(m\)-edge graph \(G\). If this named conjecture held, the same inversion used above would give

matching the BEFRS80 lower bound up to constants. This implication is (a), elementary-rigorous; the proposed stronger Ramsey bound itself is (c), conjectural.

The elementary random-coloring/alteration route behind the known universal lower bound has a specific bottleneck: at a host order proportional to \(n\), hitting every embedded copy of an \(m\)-edge graph by enough random red edges requires roughly \(mp\gtrsim n\log n\), while deleting red triangles without erasing those hits forces roughly \(p\lesssim n^{-1/2}\). Their combination is the \(m\gtrsim n^{3/2}\log n\) scale, not the desired \(n^{3/2}\sqrt{\log n}\) scale. This is (c), a structural diagnosis rather than an impossibility theorem. A semi-random or dependent construction that saves a factor \(\sqrt{\log n}\) in the simultaneous hitting step is the exact missing lemma.

Further finite computation

The next case \(n=8\) has 11,117 connected unlabeled patterns and 5,036 maximal triangle-free graphs on \(15\) vertices (the latter count is independently tabulated in BGS12). A direct Cartesian classification would require \(55,985,212\) embedding tests. At the measured \(n=7\) embedding-only rate, that is already about 1.7 core-hours before slower eight-vertex failures and graph generation; a realistic unoptimised estimate is 2–10 core-hours. It was not run under the few-minute budget, particularly because BBH98 already publishes \(F(8)=11,\ f(8)=20\). These cost figures are (d), arithmetic projections from measured throughput, not benchmark results for \(n=8\).

The uniform open problem cannot be closed by extending this census: BBH98 already reaches \(n=12\), while the number of maximal triangle-free obstruction graphs grows from 25,617 at order 16 to 1,474,647,067,521 at order 23 according to BGS12. The needed advance is theoretical—most sharply, the logarithmic improvement just isolated—not another few small cases.

PARTIAL: Verified F(7)=11 and f(7)=16 by a fresh exhaustive checker, recovered the published table through n=12, and sharpened the live-page existential bound to n^(3/2)sqrt(log n) << f(n) << n^(3/2)log n via Sudakov; the remaining wall is exactly a sqrt(log n) universal Ramsey-size gap.