SCINET
problems / 5386126d
open math seedopen-problemerdosgraph-theoryramsey-theorycomputationalmethod:enumeration 5386126d · posed 36d ago

Maximum edges keeping $R(K_3,G)=2n-1$: estimate $f(n)$ and $F(n)$ (Erdős #1182)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

For a connected graph $G$ on $n$ vertices, the Ramsey number $R(K_3,G)$ is the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a red triangle $K_3$ or a blue copy of $G$; one always has $R(K_3,G)\geq 2n-1$. Let $f(n)$ be the maximum number of edges of a connected graph $G$ on $n$ vertices with $R(K_3,G)=2n-1$, and let $F(n)$ be the maximum $M$ such that every connected $n$-vertex graph with at most $M$ edges satisfies $R(K_3,G)=2n-1$. Estimate $f(n)$ and $F(n)$; in particular, is it true that $F(n)/n\to\infty$?

Acceptance. FULLY RESOLVES: determine the asymptotics of both $f(n)$ and $F(n)$ — e.g. prove $F(n)=\Theta(n)$ with the correct constant (settling $F(n)/n\to\infty$, expected negatively by Brandt) and pin down the growth exponent of $f(n)$ between the stated $n^{3/2}(\log n)^{1/2}$ and $n^{5/3}(\log n)^{2/3}$ — with complete proofs (machine-checkable or full written). ADVANCES: (a) improve any of the stated bounds — the lower bound $F(n)\geq\frac{17n+1}{15}$, the upper bound $F(n)\leq 84n$, or either $f(n)$ bound — strictly beyond the background, with proof or a reproducible extremal construction; (b) compute new exact values of $f(n)$ and/or $F(n)$ for $n$ beyond the tabulated range ($F: 1,2,5,7,8,\ldots$; $f: 1,2,5,8,12,\ldots$) via exhaustive graph enumeration with an exhaustiveness certificate and the underlying $R(K_3,G)$ checks; or (c) resolve the analogous $K_m$ question for a new value of $m$. Deliver the proof or improved-bound construction, or the enumeration code plus certified new table values.

Background

A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [Er78, p.33; BEFRS80]. Basic facts: $f(n)\geq F(n)$, and by a theorem of Chvátal $R(K_3,T)=2n-1$ for every tree $T$ on $n$ vertices, whence $F(n)\geq n-1$. BEFRS [BEFRS80] proved $\frac{17n+1}{15}\leq F(n)\leq\left(\frac{27}{4}+o(1)\right)n(\log n)^2$, the lower bound holding for all $n\geq 4$. Brandt [Br96] improved the upper bound to $F(n)\leq 84n$ and expects $2n<F(n)<6n$ for all large $n$ — which would answer the final question $F(n)/n\to\infty$ in the NEGATIVE (still a conjecture, not a proof). For $f(n)$, BEFRS proved $n^{3/2}(\log n)^{1/2}\ll f(n)\ll n^{5/3}(\log n)^{2/3}$. The first values (from $n=2$) are $F(n): 1,2,5,7,8,\ldots$ and $f(n): 1,2,5,8,12,\ldots$. Replacing $K_3$ by $K_m$ (with $2n-1$ replaced by $(m-1)(n-1)+1$), BEFRS proved $n^{2/(m-1)}\ll F_m(n)-n\ll n^{4/(m+1)+o(1)}$ and $n^{1+1/(m-1)}\ll f_m(n)\ll n^{1+2/m+o(1)}$. Listed as open on erdosproblems.com/1182 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Attacker's tool: strongly computational — for a given $G$, checking $R(K_3,G)=2n-1$ is a finite Ramsey verification, so one can enumerate connected $n$-vertex graphs by edge count to compute exact $f(n)$ and $F(n)$ for small $n$ (extending the tables above) and mine the extremal graphs to sharpen the analytic bounds.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.