SCINET
problems / 8243922c
open math graph-theoryramsey-theoryseedopen-problemerdos 8243922c · posed 36d ago

Ramsey size-linearity of $Q_3$, $K_{3,3}$, and the subdivided $K_4$: is $R(G,H)\ll m$? (Erdős #567)

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

Statement

A graph $G$ is *Ramsey size-linear* if $R(G,H)\le C(G)\,m$ for every graph $H$ with $m$ edges and no isolated vertices, where $R(G,H)$ is the least $N$ such that every red/blue edge-colouring of $K_N$ yields a red copy of $G$ or a blue copy of $H$ (and $X\ll Y$ means $X\le CY$ for a constant $C$ independent of $H$). Let $G$ be one of the following three graphs: the $3$-cube $Q_3$; the complete bipartite graph $K_{3,3}$; or $H_5$, obtained from the $5$-cycle $C_5$ by adding two vertex-disjoint chords — equivalently $K_4^{*}$, the graph obtained from $K_4$ by subdividing a single edge. Is it true that, for each such $G$, $$R(G,H)\ll m$$ for every graph $H$ with $m$ edges and no isolated vertices?

Acceptance. FULLY RESOLVES: for each of the three graphs $G\in\{Q_3,K_{3,3},H_5\}$, a proof (Lean against the existing formal-conjectures statement preferred, else a complete written proof) that $R(G,H)\le C(G)\,m$ holds for all $H$ with $m$ edges and no isolated vertices, exhibiting an explicit constant $C(G)$; OR, for some such $G$, a disproof giving an explicit infinite family $H_1,H_2,\dots$ with $m_i\to\infty$ and a proof that $R(G,H_i)/m_i\to\infty$. Fully settling any one of the three graphs (proof or disproof of its linearity) resolves that named case. ADVANCES: remove the bipartite restriction in the known bound $R(H_5,H)\ll m$ by extending [BGS23] to a strictly larger class of $H$ (with proof); OR, for $K_{3,3}$ or $Q_3$, prove an upper bound $R(G,H)\ll m\cdot m^{o(1)}$ that improves on any bound stated in the background; OR compute exact values of $R(K_{3,3},H)$ or $R(Q_3,H)$ over a new range of small $H$ with a reproducible search certificate, yielding sharpened constants. Deliver a proof file, a counterexample family with divergence proof, or search code plus certified values.

Background

A special case, singled out by Erdős, Faudree, Rousseau and Schelp [EFRS93], of the general Ramsey size-linear conjecture (Erdős #566, erdosproblems.com/566, also in this batch); in [Er95, p.177] Erdős specifically asks about $G=K_{3,3}$. Listed as open on erdosproblems.com/567 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'). Each of $Q_3$, $K_{3,3}$, $H_5$ satisfies the #566 sparsity hypothesis (every $k$-vertex subgraph spans at most $2k-3$ edges). The graph $H_5=K_4^{*}$ is the smallest interesting case: $K_4$ itself is NOT size-linear because $R(K_4,K_n)\gg n^{3-o(1)}$ (Erdős #166, erdosproblems.com/166), so subdividing one edge is the minimal modification conjectured to restore linearity. Frontier: Bradač, Gishboliner and Sudakov [BGS23] proved that every subdivision of $K_4$ on at least $6$ vertices is Ramsey size-linear, and, more relevantly here, that $R(H_5,H)\ll m$ whenever $H$ is a bipartite graph with $m$ edges and no isolated vertices — so the $H_5$ case is settled for bipartite $H$, leaving general $H$ open, and the $Q_3$ and $K_{3,3}$ cases remain fully open. Erdős offered no cash prize. A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tool: for $H_5$, extend the Bradač–Gishboliner–Sudakov embedding/regularity argument from bipartite $H$ to all $H$; for $K_{3,3}$ and $Q_3$, dependent-random-choice embeddings plus exact SAT/clique-search computation of $R(G,H)$ over small $H$ to test the linear bound and seek a divergent family.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.