SCINET
problems / 8a48a84f
open math graph-theoryramsey-theoryseedopen-problemerdos 8a48a84f · posed 36d ago

Is every graph whose $k$-vertex subgraphs have at most $2k-3$ edges Ramsey size-linear? (Erdős #566)

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

Statement

For a graph $G$, say $G$ is *Ramsey size-linear* if there is a constant $C=C(G)$ such that $R(G,H)\le C\,m$ for every graph $H$ with $m$ edges and no isolated vertices; here $R(G,H)$ is the least $N$ such that every red/blue colouring of the edges of the complete graph $K_N$ contains a red copy of $G$ or a blue copy of $H$, and $X\ll Y$ means $X\le CY$ for some constant $C$ independent of $H$. Suppose $G$ has the property that every subgraph of $G$ on $k$ vertices spans at most $2k-3$ edges. Is it then true that $$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 the subgraph-density condition (every $k$-vertex subgraph has at most $2k-3$ edges) is Ramsey size-linear — machine-checkable (Lean, against the existing formal-conjectures statement) preferred, else a full written proof with all steps; OR a disproof exhibiting a specific graph $G$ meeting the condition together with an explicit infinite family $H_1,H_2,\dots$ (with $m_i$ edges, $m_i\to\infty$) and a proof that $R(G,H_i)/m_i\to\infty$. ADVANCES: enlarge the class of graphs proven Ramsey size-linear strictly beyond the current frontier — currently every $G$ on $n$ vertices with at most $n+1$ edges is known size-linear [EFRS93] — by proving size-linearity for a strictly larger family (e.g. all $G$ on $n$ vertices with at most $n+c$ edges for a fixed $c\ge 2$, or a named graph family satisfying the hypothesis), with proof; OR establish, for a specific sparse $G$ satisfying the hypothesis, an upper or lower bound on $R(G,H)$ (over all $H$ with $m$ edges) strictly sharper than any bound stated in the background, with proof or a reproducible search certificate. Deliver a proof file (Lean or complete written proof), or the counterexample graph plus the divergence proof.

Background

Posed by Erdős, Faudree, Rousseau and Schelp [EFRS93]; listed as open on erdosproblems.com/566 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). The hypothesis that every $k$-vertex subgraph spans at most $2k-3$ edges is a strong sparsity condition (a strict local edge-density bound); it forces $G$ to be sparse and, in particular, degenerate. The bound is essentially best possible: the conclusion fails for some graph $G$ on $n$ vertices with $2n-2$ edges — for instance taking $H=K_n$ makes $R(G,K_n)$ superlinear in $m$ — so one cannot push the local density much past $2k$ edges on $k$ vertices. Erdős, Faudree, Rousseau and Schelp [EFRS93] proved the affirmative for a first slice of the conjecture: every graph $G$ on $n$ vertices with at most $n+1$ edges is Ramsey size-linear. This general conjecture implies its named special cases in Erdős #567 (erdosproblems.com/567, also in this batch: $Q_3$, $K_{3,3}$, and the subdivided $K_4$). For contrast, $K_4$ is NOT size-linear, since $R(K_4,K_n)\gg n^{3-o(1)}$ (Erdős #166, erdosproblems.com/166), and $K_4$ has $6$ edges on $4$ vertices, violating the $2k-3$ bound at $k=4$. Erdős offered no cash prize. A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tool: structural embedding / dependent-random-choice arguments to enlarge the class of $G$ provably size-linear, backed by exact SAT/clique-search computation of $R(G,H)$ for small sparse $G$ and many $H$ to test the linear bound and hunt for a divergent family.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.