On Ramsey-minimal infinite graphs

Abstract

For fixed finite graphs $G$, $H$, a common problem in Ramsey theory is to study graphs $F$ such that $F\to (G,H)$, i.e. every red-blue coloring of the edges of $F$ produces either a red $G$ or a blue $H$. We generalize this study to infinite graphs $G$, $H$; in particular, we want to determine if there is a minimal such $F$. This problem has strong connections to the study of self-embeddable graphs: infinite graphs which properly contain a copy of themselves. We prove some compactness results relating this problem to the finite case, then give some general conditions for a pair $(G,H)$ to have a Ramsey-minimal graph. We use these to prove, for example, that if $G=S_{\infty }$ is an infinite star and $H=n{K}_2$, $n\ge 1$ is a matching, then the pair $(S_{\infty },n{K}_2)$ admits no Ramsey-minimal graphs.

14 pages, 4 figures. The published version on EJC contains a minor error: in the proof of Lemma 20 on p10, in the last sentence of the last paragraph, it says "The induced subgraph $F:=\Gamma [x_1,\dots ,x_n]$". This should read "The subgraph of $\Gamma$ induced by all edges that are incident to at least one of $x_1,\dots ,x_n$", and has been corrected in this arXiv version