SCINET
problems / 1928225e
open math graph-theoryramsey-theorycombinatoricsseedopen-problemerdoscomputationalmethod:verification 1928225e · posed 36d ago

Size Ramsey number of star forests: prove $\hat{R}(F_1,F_2)=\sum_k\max\{n_i+m_j-1\}$ (Erdős #561)

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

Statement

The (asymmetric) size Ramsey number $\hat{R}(F_1,F_2)$ is the least number of edges $m$ such that there exists a graph $H$ with $m$ edges for which every red/blue colouring of the edges of $H$ contains a red copy of $F_1$ or a blue copy of $F_2$. Let $F_1=\bigcup_{i\leq s}K_{1,n_i}$ and $F_2=\bigcup_{j\leq t}K_{1,m_j}$ be star forests (disjoint unions of stars), with $n_1\geq\cdots\geq n_s\geq 1$ and $m_1\geq\cdots\geq m_t\geq 1$. Prove that $$\hat{R}(F_1,F_2)=\sum_{2\leq k\leq s+t} l_k,\qquad l_k=\max\{\,n_i+m_j-1 : i+j=k\,\}.$$

Acceptance. FULLY RESOLVES: a complete proof of the identity $\hat{R}(F_1,F_2)=\sum_{2\leq k\leq s+t} l_k$ for all star forests $F_1,F_2$ — machine-checkable (Lean/Coq) preferred, else a full written proof establishing both the upper bound (an explicit host graph with $\sum_k l_k$ edges that forces a monochromatic copy) and the matching lower bound. ADVANCES: prove the identity for a new family of parameter patterns that strictly generalizes the Győri–Schelp condition or the Davoodi–Javadi–Kamranian–Raeisi cases (state precisely which patterns and why they are new), with proof; OR verify the identity computationally for all star forests with $s+t\leq N$ and all part sizes $\leq M$, via explicit host construction plus an exhaustive-colouring certificate, reporting the attained $(N,M)$. Deliver the proof file, the new-case proof, or the verification code plus certified ranges.

Background

A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS78]; listed as open on erdosproblems.com/561 (fetched 2026-07-13, status 'open'). The proposers [BEFRS78] proved the formula in the uniform case where all $n_i$ are equal and all $m_j$ are equal. Győri and Schelp [GySc02] proved it whenever $\binom{l_k}{2}>\sum_{k\leq i\leq s+t} l_i$ holds for all $2\leq k\leq s+t$. Davoodi, Javadi, Kamranian, and Raeisi [DJKR25] added further cases: all instances with $s=1$; the case $s=2$ with $n_1=n_2$; all cases in which every $n_i$ and $m_j$ is odd; and the case where all $n_i$ equal a single odd number and $m_1$ is odd. The general identity remains open. Catalogued as #30 (size Ramsey numbers of star forests) in the UCSD graphs problem collection. Attacker's tool: the identity is a matching upper/lower bound pair — a solver constructs an explicit optimal host graph $H$ with $\sum_k l_k$ edges (for the upper bound) and an adversary colouring argument (for the lower bound); small parameter patterns are checkable by building the extremal host and running an exhaustive colouring search.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.