Do linear tree-Ramsey and quadratic clique-Ramsey together force Ramsey size-linearity? (Erdős #568)
Statement
For graphs $G,H$ let $R(G,H)$ be the least $N$ such that every red/blue colouring of the edges of $K_N$ contains a red copy of $G$ or a blue copy of $H$, and write $X\ll Y$ to mean $X\le CY$ for a constant $C$ independent of the varying parameter. Let $G$ be a graph such that (i) $R(G,T_n)\ll n$ for every tree $T_n$ on $n$ vertices, and (ii) $R(G,K_n)\ll n^2$. Is it true that then $G$ is *Ramsey size-linear*, i.e. $$R(G,H)\ll m$$ for every graph $H$ with $m$ edges and no isolated vertices?
Acceptance. FULLY RESOLVES: a complete proof that every graph $G$ satisfying both hypotheses $R(G,T_n)\ll n$ (all trees $T_n$) and $R(G,K_n)\ll n^2$ is Ramsey size-linear — machine-checkable (Lean) preferred, else a full written proof; OR a disproof exhibiting a specific graph $G$ that satisfies both hypotheses together with an explicit infinite family $H_1,H_2,\dots$ ($m_i$ edges, $m_i\to\infty$) and a proof that $R(G,H_i)/m_i\to\infty$. ADVANCES: prove the implication under an additional natural restriction on $G$ (e.g. $G$ bipartite, or $G$ of bounded degeneracy), with proof; OR prove a size-linear bound $R(G,H)\ll m\cdot m^{o(1)}$ from the two endpoint hypotheses that improves on any bound derivable from the background; OR identify, with a reproducible search certificate, a candidate graph $G$ meeting both hypotheses on all computationally accessible instances, as evidence for the extremal case. Deliver a proof file, or the counterexample graph plus divergence proof, or the near-extremal candidate with certificate.
Background
Posed by Erdős, Faudree, Rousseau and Schelp [EFRS93]; listed as open on erdosproblems.com/568 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). This is a structural sharpening of the general Ramsey size-linear conjecture (Erdős #566, erdosproblems.com/566, also in this batch): it asks whether size-linearity is already forced by good behaviour against the two extreme families of second graphs — sparse spread-out targets (trees $T_n$, which have $n-1$ edges, so a linear bound $R(G,T_n)\ll n$ is size-linear against trees) and the densest targets (cliques $K_n$, which have $\binom{n}{2}\asymp n^2$ edges, so $R(G,K_n)\ll n^2$ is size-linear against cliques). The question is whether controlling these two endpoints propagates to all $H$ with $m$ edges. The hypotheses (i) and (ii) are exactly the size-linear bounds specialised to $H=T_n$ and $H=K_n$; a graph failing size-linearity while satisfying both would show the endpoints do not suffice. Erdős, Faudree, Rousseau and Schelp are the authors of the surrounding programme (see also the $n+1$-edge result of [EFRS93] recorded under Erdős #566). Erdős offered no cash prize. The attacker's tool: interpolation/embedding arguments passing from the tree and clique endpoints to general $H$ via decomposition of $H$ into sparse and dense parts, tested against exact SAT/clique-search computation of $R(G,H)$ for candidate graphs $G$ that satisfy the endpoint bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #568 (T. F. Bloom) | website |
| REF-02 | Ramsey Theory #33 (Erdős graphs problem collection) — tree/clique endpoints and size-linearity | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.