Erdős Problem #550

Erdős Problem 550 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open (Lean). Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/550.tex.

REUSED SOURCE 1

Let $m_1\leq \ldots \leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that \[ R(T,G) \leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1. \]

Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.

1) “FORMAL RESTATEMENT”

Let $m_1\le \cdots \le m_k$ be fixed positive integers, and let $T$ be a tree on $n$ vertices. Let $G$ be the complete $k$-partite graph with part sizes $m_1,\dots,m_k$ (so $\chi(G)=k$).

The task is to prove that for $n$ sufficiently large, \[ R(T,G)\ \le\ (k-1)\left(R(T,K_{m_1,m_2})-1\right)+m_1. \] Here $R(T,G)$ is the two-colour Ramsey number: the smallest $N$ such that every red/blue colouring of $E(K_N)$ contains either a red copy of $T$ or a blue copy of $G$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The only external fact stated in the problem file is Chvátal's theorem: for a tree $T$ on $n$ vertices, \[ R(T,K_m)=(m-1)(n-1)+1. \] I will not assume any other literature.

3) “ATTACK PLAN”

Try to relate the multipartite target $G$ to the bipartite target $K_{m_1,m_2}$ via monotonicity and structural reductions (e.g. by finding $k$ vertex sets with all cross-edges blue). A natural approach is to study the red graph $R$ of a colouring: if $R$ has many connected components, then cross-edges between components are automatically blue, giving multipartite structure; if $R$ has few components, then some component is large and (since it avoids a red $T$) should contain a blue $K_{m_1,m_2}$ by the definition of $R(T,K_{m_1,m_2})$. One would then try to combine this internal bipartite structure with other components to build the full $k$-partite $G$.

I was not able to complete the last step.

4) “WORK”

Set \[ R_0 := R(T,K_{m_1,m_2}). \]

Lemma 1 (Monotonicity in the blue target). If $H$ is a subgraph of $G$ (i.e. $H$ can be obtained from $G$ by deleting vertices and/or edges), then \[ R(T,H)\le R(T,G). \]

Proof. Let $N=R(T,G)$. In any red/blue colouring of $K_N$, either there is a red copy of $T$ or a blue copy of $G$. In the latter case, since $H$ is a subgraph of $G$, the same vertex set contains a blue copy of $H$ by restricting to the vertices/edges corresponding to $H$. Hence $N$ also witnesses the Ramsey property for $(T,H)$, so $R(T,H)\le N=R(T,G)$. $\square$

Lemma 2 (For $n$ large, the parts $m_i$ are bounded by $R_0-1$). For every $n$ and every $m_1,m_2$, we have $R_0\ge n$. In particular, if $n\ge m_k+1$ then $R_0-1\ge m_k\ge m_i$ for all $i\ge 2$.

Proof. By definition, $R_0$ is the smallest $N$ such that every colouring of $K_N$ contains a red copy of $T$ or a blue copy of $K_{m_1,m_2}$. If $N<n$, then $K_N$ does not even have enough vertices to host a copy of $T$, so colouring all edges red produces a colouring with no red $T$ and (since there are no blue edges) no blue $K_{m_1,m_2}$. Hence $N<n$ cannot satisfy the Ramsey property, so $R_0\ge n$.

If $n\ge m_k+1$ then $R_0\ge n\ge m_k+1$ and thus $R_0-1\ge m_k$. $\square$

Lemma 3 (Red components yield blue complete multipartite subgraphs). Fix a red/blue colouring of $K_N$ and let $R$ be the graph of red edges. Let $C_1,\dots,C_s$ be vertex-disjoint sets such that there are no red edges between $C_i$ and $C_j$ for $i\neq j$ (for instance, distinct connected components of $R$). Then every edge between $C_i$ and $C_j$ is blue, and therefore for any choice of subsets $C_i'\subseteq C_i$ the blue graph contains the complete multipartite graph with parts $C_1',\dots,C_s'$.

Proof. If there is no red edge between $C_i$ and $C_j$, then every edge between them must be blue because every edge of $K_N$ is coloured either red or blue. Thus all cross-edges between the parts are blue, exactly as required for a blue copy of the corresponding complete multipartite graph. $\square$

Lemma 4 (Sanity check: the inequality matches Chvátal for cliques). If $m_1=m_2=\cdots=m_k=1$, then $G=K_k$ and the claimed inequality becomes \[ R(T,K_k)\le (k-1)(R(T,K_2)-1)+1. \] Moreover $R(T,K_2)=n$, so the right-hand side equals $(k-1)(n-1)+1$, which is exactly Chvátal's value of $R(T,K_k)$.

Proof. $K_2$ is a single edge. In any colouring of $K_n$, either there is a blue edge or all edges are red; in the latter case the red graph is $K_n$ and contains $T$ (since $|T|=n$). Thus $R(T,K_2)=n$. Substituting gives $(k-1)(n-1)+1$, matching the stated Chvátal theorem. $\square$

Where the proof gets stuck. Assume $n\ge m_k+1$ so that $m_i\le R_0-1$ for all $i\ge 2$ (Lemma 2). By Lemma 1, it would suffice to prove an inequality for a larger complete multipartite graph whose $(k-1)$ largest parts are all size $R_0-1$, but I do not see how to force such a multipartite structure from the hypothesis “no red $T$” using only the information encoded in $R_0$.

5) “VERIFICATION”

Fast sanity checks: - For $k=2$ the inequality reads $R(T,K_{m_1,m_2})\le (1)(R(T,K_{m_1,m_2})-1)+m_1$, which is tautologically true. - For $m_1=\cdots=m_k=1$ (so $G=K_k$), Lemma 4 shows the inequality holds with equality and is consistent with Chvátal.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1–3 give a structural reduction toolkit: monotonicity in the blue target, the bound $R(T,K_{m_1,m_2})\ge n$, and the fact that vertex sets with no red edges between them automatically form a blue complete multipartite graph. Lemma 4 verifies the claimed inequality matches the known exact formula when $G$ is a clique.

(ii) First gap (crisp): Given a red/blue colouring of $K_N$ with $N=(k-1)(R_0-1)+m_1$ and with no red $T$, prove that the blue graph must contain $K_{m_1,\dots,m_k}$. Equivalently, from “no red $T$” plus the definition of $R_0$, extract $k$ disjoint vertex sets $V_1,\dots,V_k$ with $|V_i|=m_i$ such that all cross-edges between $V_i$ and $V_j$ are blue.

(iii) Top 3 next moves: 1. Component-splitting strategy: Formalise an induction on $k$ using the red component decomposition. Show that if the red graph has too few components, then a large component must contain a blue $K_{m_1,m_2}$; then prove a lemma that this internal bipartite structure can be combined with other red components (or further splittings) to create the full $k$-partite $G$. 2. Minimal counterexample analysis: Assume a smallest $N$ and a counterexample colouring on $N-1$ vertices exists. Derive necessary structure (e.g. constraints on the sizes/number of red components and on where blue $K_{m_1,m_2}$ copies can occur) and attempt to contradict the vertex count $N-1$. 3. Special cases: Prove the inequality for $k=3$ first (tripartite $G$), or for restricted multipartite shapes (e.g. $m_2=\cdots=m_k$), then attempt to bootstrap to general $m_3,\dots,m_k$ via Lemma 1.

(iv) Minimal counterexample structure: A counterexample would be a 2-colouring of $K_{N-1}$, where $N=(k-1)(R_0-1)+m_1$, with no red copy of the given $n$-vertex tree $T$ and no blue copy of the complete $k$-partite graph with part sizes $m_1,\dots,m_k$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Let $m_1\leq \ldots \leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that \[ R(T,G) \leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1. \]

Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.

1) “FORMAL RESTATEMENT”

Let $m_1\le \cdots \le m_k$ be fixed positive integers, and let $T$ be a tree on $n$ vertices. Let $G$ be the complete $k$-partite graph with part sizes $m_1,\dots,m_k$ (so $\chi(G)=k$).

The task is to prove that for $n$ sufficiently large, \[ R(T,G)\ \le\ (k-1)\left(R(T,K_{m_1,m_2})-1\right)+m_1. \] Here $R(T,G)$ is the two-colour Ramsey number: the smallest $N$ such that every red/blue colouring of $E(K_N)$ contains either a red copy of $T$ or a blue copy of $G$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The only external fact stated in the problem file is Chvátal's theorem: for a tree $T$ on $n$ vertices, \[ R(T,K_m)=(m-1)(n-1)+1. \] I will not assume any other literature.

3) “ATTACK PLAN”

Try to relate the multipartite target $G$ to the bipartite target $K_{m_1,m_2}$ via monotonicity and structural reductions (e.g. by finding $k$ vertex sets with all cross-edges blue). A natural approach is to study the red graph $R$ of a colouring: if $R$ has many connected components, then cross-edges between components are automatically blue, giving multipartite structure; if $R$ has few components, then some component is large and (since it avoids a red $T$) should contain a blue $K_{m_1,m_2}$ by the definition of $R(T,K_{m_1,m_2})$. One would then try to combine this internal bipartite structure with other components to build the full $k$-partite $G$.

I was not able to complete the last step.

4) “WORK”

Set \[ R_0 := R(T,K_{m_1,m_2}). \]

Lemma 1 (Monotonicity in the blue target). If $H$ is a subgraph of $G$ (i.e. $H$ can be obtained from $G$ by deleting vertices and/or edges), then \[ R(T,H)\le R(T,G). \]

Proof. Let $N=R(T,G)$. In any red/blue colouring of $K_N$, either there is a red copy of $T$ or a blue copy of $G$. In the latter case, since $H$ is a subgraph of $G$, the same vertex set contains a blue copy of $H$ by restricting to the vertices/edges corresponding to $H$. Hence $N$ also witnesses the Ramsey property for $(T,H)$, so $R(T,H)\le N=R(T,G)$. $\square$

Lemma 2 (For $n$ large, the parts $m_i$ are bounded by $R_0-1$). For every $n$ and every $m_1,m_2$, we have $R_0\ge n$. In particular, if $n\ge m_k+1$ then $R_0-1\ge m_k\ge m_i$ for all $i\ge 2$.

Proof. By definition, $R_0$ is the smallest $N$ such that every colouring of $K_N$ contains a red copy of $T$ or a blue copy of $K_{m_1,m_2}$. If $N<n$, then $K_N$ does not even have enough vertices to host a copy of $T$, so colouring all edges red produces a colouring with no red $T$ and (since there are no blue edges) no blue $K_{m_1,m_2}$. Hence $N<n$ cannot satisfy the Ramsey property, so $R_0\ge n$.

If $n\ge m_k+1$ then $R_0\ge n\ge m_k+1$ and thus $R_0-1\ge m_k$. $\square$

Lemma 3 (Red components yield blue complete multipartite subgraphs). Fix a red/blue colouring of $K_N$ and let $R$ be the graph of red edges. Let $C_1,\dots,C_s$ be vertex-disjoint sets such that there are no red edges between $C_i$ and $C_j$ for $i\neq j$ (for instance, distinct connected components of $R$). Then every edge between $C_i$ and $C_j$ is blue, and therefore for any choice of subsets $C_i'\subseteq C_i$ the blue graph contains the complete multipartite graph with parts $C_1',\dots,C_s'$.

Proof. If there is no red edge between $C_i$ and $C_j$, then every edge between them must be blue because every edge of $K_N$ is coloured either red or blue. Thus all cross-edges between the parts are blue, exactly as required for a blue copy of the corresponding complete multipartite graph. $\square$

Lemma 4 (Sanity check: the inequality matches Chvátal for cliques). If $m_1=m_2=\cdots=m_k=1$, then $G=K_k$ and the claimed inequality becomes \[ R(T,K_k)\le (k-1)(R(T,K_2)-1)+1. \] Moreover $R(T,K_2)=n$, so the right-hand side equals $(k-1)(n-1)+1$, which is exactly Chvátal's value of $R(T,K_k)$.

Proof. $K_2$ is a single edge. In any colouring of $K_n$, either there is a blue edge or all edges are red; in the latter case the red graph is $K_n$ and contains $T$ (since $|T|=n$). Thus $R(T,K_2)=n$. Substituting gives $(k-1)(n-1)+1$, matching the stated Chvátal theorem. $\square$

Where the proof gets stuck. Assume $n\ge m_k+1$ so that $m_i\le R_0-1$ for all $i\ge 2$ (Lemma 2). By Lemma 1, it would suffice to prove an inequality for a larger complete multipartite graph whose $(k-1)$ largest parts are all size $R_0-1$, but I do not see how to force such a multipartite structure from the hypothesis “no red $T$” using only the information encoded in $R_0$.

5) “VERIFICATION”

Fast sanity checks: - For $k=2$ the inequality reads $R(T,K_{m_1,m_2})\le (1)(R(T,K_{m_1,m_2})-1)+m_1$, which is tautologically true. - For $m_1=\cdots=m_k=1$ (so $G=K_k$), Lemma 4 shows the inequality holds with equality and is consistent with Chvátal.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1–3 give a structural reduction toolkit: monotonicity in the blue target, the bound $R(T,K_{m_1,m_2})\ge n$, and the fact that vertex sets with no red edges between them automatically form a blue complete multipartite graph. Lemma 4 verifies the claimed inequality matches the known exact formula when $G$ is a clique.

(ii) First gap (crisp): Given a red/blue colouring of $K_N$ with $N=(k-1)(R_0-1)+m_1$ and with no red $T$, prove that the blue graph must contain $K_{m_1,\dots,m_k}$. Equivalently, from “no red $T$” plus the definition of $R_0$, extract $k$ disjoint vertex sets $V_1,\dots,V_k$ with $|V_i|=m_i$ such that all cross-edges between $V_i$ and $V_j$ are blue.

(iii) Top 3 next moves: 1. Component-splitting strategy: Formalise an induction on $k$ using the red component decomposition. Show that if the red graph has too few components, then a large component must contain a blue $K_{m_1,m_2}$; then prove a lemma that this internal bipartite structure can be combined with other red components (or further splittings) to create the full $k$-partite $G$. 2. Minimal counterexample analysis: Assume a smallest $N$ and a counterexample colouring on $N-1$ vertices exists. Derive necessary structure (e.g. constraints on the sizes/number of red components and on where blue $K_{m_1,m_2}$ copies can occur) and attempt to contradict the vertex count $N-1$. 3. Special cases: Prove the inequality for $k=3$ first (tripartite $G$), or for restricted multipartite shapes (e.g. $m_2=\cdots=m_k$), then attempt to bootstrap to general $m_3,\dots,m_k$ via Lemma 1.

(iv) Minimal counterexample structure: A counterexample would be a 2-colouring of $K_{N-1}$, where $N=(k-1)(R_0-1)+m_1$, with no red copy of the given $n$-vertex tree $T$ and no blue copy of the complete $k$-partite graph with part sizes $m_1,\dots,m_k$.