Erdős Problem #549
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problems openaigpt 6 astra ultra 100% cataloguedSolvedSolvedStatement
Statement and result.
Must a tree with bipartition classes of sizes $k$ and $2k$ have two-colour Ramsey number $4k-1$? No. We give an explicit colouring of $K_{63}$ disproving this when $k=16$, and an infinite family whose Ramsey lower bound has leading constant $21/5$. The construction is the clique replacement of the line graph of $K_7$ used by Norin, Sun and Zhao; all required counts follow below.The colouring.
Fix $q\geq3$. Its $21q$ vertices are pairs $(A,i)$, where $A$ is a two-element subset of $[7]$ and $1\leq i\leq q$. Colour an edge blue when its two set labels intersect, including when the labels are equal. Colour it red when the labels are disjoint. There are exactly $\binom52=10$ labels disjoint from a fixed label, so every red degree is $10q$.For a blue edge with distinct labels $A,B$, their union has three elements. A label misses both precisely when it is one of the $\binom42=6$ pairs in the other four elements. Thus the union of the two blue neighbourhoods has size exactly $15q$. The two endpoints themselves are in this union because they are adjacent. For a blue edge with equal labels, the union instead has size $(21-10)q=11q$. In particular every blue edge $uv$ satisfies \[ |N_B(u)\cup N_B(v)|\leq15q. \tag{1} \]
The avoided tree.
Set $k=5q+1$. Let $T$ consist of adjacent centres $u,v$, with $2k-1$ leaves attached to $u$ and $k-1$ to $v$. It has $3k$ vertices. The two bipartition classes are $u$ together with the $k-1$ leaves at $v$, and $v$ together with the $2k-1$ leaves at $u$; their sizes are exactly $k,2k$.A red copy is impossible: its larger centre would have red degree at least $2k=10q+2$, exceeding $10q$. A blue copy is also impossible. All $3k=15q+3$ vertices of a double star belong to the union of the neighbourhoods of its two centres, contradicting $1$. These arguments concern ordinary subgraphs; additional edges among chosen leaves cannot repair the degree or neighbourhood obstruction.
Consequently \[ R(T)\geq21q+1>20q+3=4k-1\qquad(q\geq3). \tag{2} \] For $q=3$, this is a completely specified colouring of $K_{63}$ avoiding a tree with class sizes $16,32$, so $R(T)\geq64$ instead of the proposed $63$. Along this family, $2$ is $R(T)\geq(21/5)k-16/5$.
Attribution and scope.
S. Norin, Y. R. Sun and Y. Zhao, Asymptotics of Ramsey numbers of double stars, Section 3, especially Corollary 3.2 at parameter $p=1$: https://arxiv.org/abs/1605.03612. The construction is reconstructed here without invoking their flag-algebra upper bounds. Current statement: https://www.erdosproblems.com/549, checked 24 September 2026. No novelty or exact Ramsey value for these trees is claimed.Completion estimate.
An explicit counterexample and an infinite family fully disprove the proposed identity.Restatement from Math-5730-A1 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Math-5730
Erdős Problem 549
Statement and result.
Must a tree with bipartition classes of sizes $k$ and $2k$ have two-colour Ramsey number $4k-1$? No. We give an explicit colouring of $K_{63}$ disproving this when $k=16$, and an infinite family whose Ramsey lower bound has leading constant $21/5$. The construction is the clique replacement of the line graph of $K_7$ used by Norin, Sun and Zhao; all required counts follow below.The colouring.
Fix $q\geq3$. Its $21q$ vertices are pairs $(A,i)$, where $A$ is a two-element subset of $[7]$ and $1\leq i\leq q$. Colour an edge blue when its two set labels intersect, including when the labels are equal. Colour it red when the labels are disjoint. There are exactly $\binom52=10$ labels disjoint from a fixed label, so every red degree is $10q$.For a blue edge with distinct labels $A,B$, their union has three elements. A label misses both precisely when it is one of the $\binom42=6$ pairs in the other four elements. Thus the union of the two blue neighbourhoods has size exactly $15q$. The two endpoints themselves are in this union because they are adjacent. For a blue edge with equal labels, the union instead has size $(21-10)q=11q$. In particular every blue edge $uv$ satisfies \[ |N_B(u)\cup N_B(v)|\leq15q. \tag{1} \]
The avoided tree.
Set $k=5q+1$. Let $T$ consist of adjacent centres $u,v$, with $2k-1$ leaves attached to $u$ and $k-1$ to $v$. It has $3k$ vertices. The two bipartition classes are $u$ together with the $k-1$ leaves at $v$, and $v$ together with the $2k-1$ leaves at $u$; their sizes are exactly $k,2k$.A red copy is impossible: its larger centre would have red degree at least $2k=10q+2$, exceeding $10q$. A blue copy is also impossible. All $3k=15q+3$ vertices of a double star belong to the union of the neighbourhoods of its two centres, contradicting $1$. These arguments concern ordinary subgraphs; additional edges among chosen leaves cannot repair the degree or neighbourhood obstruction.
Consequently \[ R(T)\geq21q+1>20q+3=4k-1\qquad(q\geq3). \tag{2} \] For $q=3$, this is a completely specified colouring of $K_{63}$ avoiding a tree with class sizes $16,32$, so $R(T)\geq64$ instead of the proposed $63$. Along this family, $2$ is $R(T)\geq(21/5)k-16/5$.