Problems in Graph Theory from Memphis

NEW

Problem: Reconstruct $\hat r(G,tK_2)$ as the size Ramsey number: the minimum number of edges in a graph $F$ such that every red/blue coloring of $E(F)$ contains a red copy of $G$ or a blue matching of size $t$. In the Memphis “graph versus matching” notation, $\hat r_\infty(G)$ is the normalized asymptotic value

using the standard upper bound given by $t$ disjoint copies of $G$.

The literal question asks whether $\hat r_\infty(G_n)\to0$ for every graph sequence with $|V(G_n)|\to\infty$ and bounded maximum degree.

Result: The literal statement is false because isolated vertices are not excluded.

Let

where $P_3$ is the path on three vertices and $I_m$ is an independent set of $m$ isolated vertices. Then $|V(G_m)|=m+3\to\infty$ and $\Delta(G_m)=2$, but

for every $m$.

Indeed, first

The upper bound is given by $t$ disjoint copies of $P_3$: if no copy is entirely red, each copy contributes a blue edge, giving a blue $tK_2$. The lower bound follows because if $F$ has fewer than $2t$ edges, take a maximum matching $M$. If $\nu(F)<t$, color all edges blue. Otherwise color the edges of $M$ red and all other edges blue; the red graph is a matching, hence has no red $P_3$, and the blue graph has fewer than $t$ edges, hence no blue $tK_2$.

Now fix $m$. For all sufficiently large $t$, $t$ disjoint copies of $P_3$ have enough vertices to realize the isolated vertices of $G_m$. Thus

for all large $t$. Since $|E(G_m)|=2$,

So the proposed universal limit $0$ fails. The defect is the missing exclusion of isolated vertices; size Ramsey numbers count edges, so arbitrarily many isolated vertices may be appended without changing the normalized asymptotic parameter. A natural repair is to require the number of non-isolated vertices, or equivalently $|E(G_n)|$ under bounded degree and no isolated vertices, to tend to infinity.

Citation: No external citation needed; the counterexample is elementary.