codex 5.2 extra high attempt on Math-854

1) FORMAL RESTATEMENT

Fix a (simple, undirected) finite graph $G$. For two graphs $A,B$, write $R(A,B)$ for the least integer $N$ such that every red/blue colouring of the edges of the complete graph $K_N$ contains either a red copy of $A$ or a blue copy of $B$.

Assume that $G$ satisfies the following two growth conditions.

(A) There exists a constant $c_T(G)>0$ such that for every $n\ge 1$ and every tree $T_n$ on $n$ vertices, \[ R(G,T_n) \le c_T(G)\,n. \]

(B) There exists a constant $c_K(G)>0$ such that for every $n\ge 1$, \[ R(G,K_n) \le c_K(G)\,n^2. \]

Question: Does there exist a constant $c(G)>0$ such that for every graph $H$ with $m=e(H)$ edges and with no isolated vertices, \[ R(G,H) \le c(G)\,m? \] (Equivalently: under (A) and (B), is $G$ Ramsey size linear?)

2) QUICK LITERATURE/CONTEXT CHECK

Only the definitions and claims explicitly present in the provided problem file are treated as "given". (No external theorems are invoked as black boxes.)

3) ATTACK PLAN

If the statement is true, a natural strategy is:

- Use (A) to deduce that in any colouring of $K_N$ with no red $G$, the blue graph is "tree-universal" up to order about $N/c_T(G)$.

- Use (B) to deduce that in any colouring of $K_N$ with no red $G$, the blue graph contains a clique of order about $\sqrt{N/c_K(G)}$.

- Try to embed a general $m$-edge graph $H$ into such a blue graph using a decomposition of $H$ into a tree-like backbone plus additional edges that can be routed inside the forced clique.

If the statement is false, one should look for a graph $G$ satisfying (A) and (B) but for which there exists a sparse (many-vertex) graph $H$ with $m$ edges and $R(G,H)\gg m$.

4) WORK

Fast reality check / sanity checks.

- If $G=K_2$ (a single edge), then $R(K_2,T_n)=n$ for every tree $T_n$, and $R(K_2,K_n)=n$. For any $H$ with no isolated vertices and $m=e(H)$, we have \[ R(K_2,H)=|V(H)|\le 2m \] (see Lemma 568.1 below), so $K_2$ is Ramsey size linear.

- Condition (B) alone implies a quadratic-in-$m$ bound for all $H$ (Lemma 568.2). Condition (A) alone implies a linear-in-$m$ bound for forests (Lemma 568.3). The hard part is controlling arbitrary extra edges beyond a forest.

Lemma 568.1 (vertex bound from "no isolated vertices"). If $H$ is a graph with $m=e(H)$ edges and no isolated vertices, then \[ |V(H)| \le 2m. \]

Proof. Let $n=|V(H)|$. By the handshake lemma, the sum of degrees is \[ \sum_{v\in V(H)} \deg_H(v)=2m. \] If $H$ has no isolated vertices then $\deg_H(v)\ge 1$ for every $v$, hence \[ 2m=\sum_{v\in V(H)} \deg_H(v) \ge \sum_{v\in V(H)} 1 = n. \] So $n\le 2m$ as claimed. $\square$

Lemma 568.2 (quadratic bound from (B)). Assume (B): $R(G,K_n)\le c_K(G)n^2$ for all $n$. Then for every graph $H$ with $m=e(H)$ edges and no isolated vertices, \[ R(G,H) \le 4c_K(G)\,m^2. \]

Proof. Let $n=|V(H)|$. Since $H$ is a subgraph of the complete graph $K_n$, any blue copy of $K_n$ contains a blue copy of $H$. Therefore, by monotonicity in the second argument, \[ R(G,H) \le R(G,K_n). \] By (B), $R(G,K_n)\le c_K(G)n^2$. By Lemma 568.1, $n\le 2m$, hence \[ R(G,H) \le c_K(G)n^2 \le c_K(G)(2m)^2 = 4c_K(G)m^2. \] $\square$

Lemma 568.3 (linear bound for forests from (A)). Assume (A): $R(G,T_n)\le c_T(G)n$ for all $n$ and all trees $T_n$ on $n$ vertices. Let $F$ be any forest with $m=e(F)$ edges and no isolated vertices. Then \[ R(G,F) \le 2c_T(G)\,m. \]

Proof. Let $n=|V(F)|$. By Lemma 568.1, $n\le 2m$.

We first construct a tree $T$ on the same vertex set $V(F)$ such that $F\subseteq T$ as graphs. Write the components of $F$ as $F_1,\dots,F_r$ with vertex sets $V_1,\dots,V_r$ (so $r\ge 1$ and the $V_i$ partition $V(F)$). For $i=1,\dots,r-1$ choose vertices $x_i\in V_i$ and $y_i\in V_{i+1}$ and add the edge $x_iy_i$. Let $T$ be the graph obtained from $F$ by adding these $r-1$ edges. Then $T$ is connected (it links the components in a chain) and acyclic (adding an edge between distinct components cannot create a cycle). Hence $T$ is a tree on $n$ vertices, and clearly $F\subseteq T$.

Now use monotonicity in the second argument again: since $F\subseteq T$, \[ R(G,F) \le R(G,T). \] By (A), $R(G,T)\le c_T(G)\,n \le c_T(G)\,(2m)=2c_T(G)m$. $\square$

Remark (cliques also give linear-in-$m$ bounds). For $H=K_t$, we have $m=\binom t2$ and (B) gives $R(G,K_t)\le c_K(G)t^2\le 2c_K(G)\,m$ for all $t\ge 2$.

5) VERIFICATION

- Lemma 568.1 uses only the handshake lemma and the assumption "no isolated vertices".

- Monotonicity used in Lemma 568.2 and Lemma 568.3: if $H\subseteq H'$, then every blue $H'$ contains a blue $H$, so $R(G,H)\le R(G,H')$.

- Lemma 568.3 explicitly constructs $T$ and checks connectivity and acyclicity.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here: under (B) we always have the quadratic size bound \[ R(G,H)\le 4c_K(G)m^2\qquad (H\text{ has }m\text{ edges and no isolated vertices}), \] and under (A) we have the linear bound $R(G,F)\le 2c_T(G)m$ for every forest $F$ with $m$ edges and no isolated vertices.

(ii) First gap (crisp): show how to use the forced presence of every $n$-vertex tree (for $n\asymp N$) together with a forced blue clique of size $\asymp\sqrt N$ to embed an arbitrary $m$-edge graph $H$ when $N\asymp m$.

(iii) Top 3 next moves:

1. Prove an embedding lemma of the form: if a graph $B$ on $N$ vertices is universal for all trees on $\ge \alpha N$ vertices and contains a clique of size $\ge \beta\sqrt N$, then $B$ contains every $m$-edge graph $H$ with no isolated vertices for $N\ge C(\alpha,\beta)m$.

2. Try to reduce general $H$ to a bounded number of "tree + dense core" pieces (e.g. via finding a small vertex cover or large matching) and show each piece can be embedded using (A) and (B).

3. For a potential disproof, search for a candidate $G$ satisfying (A) and (B) and construct $H$ with $m$ edges but with large unavoidable obstruction to appearing in complements of $G$-free graphs (e.g. $H$ with very large "tree-universality" requirements but small $m$).

(iv) Minimal counterexample structure (if false): a fixed graph $G$ satisfying (A) and (B) together with a family $H_m$ with $e(H_m)=m$, no isolated vertices, and colourings of $K_{c m}$ with no red $G$ and no blue $H_m$ for arbitrarily large $m$. Such an $H_m$ would have to avoid the simple "forest" and "clique" mechanisms captured by Lemmas 568.2--568.3.