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=nK_2$, $n \geqslant 1$ is a matching, then the pair $(S_\infty,nK_2)$ admits no Ramsey-minimal graphs.
@article{10_37236_10046,
author = {Jordan Barrett and Valentino Vito},
title = {On {Ramsey-minimal} infinite graphs},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/10046},
zbl = {1464.05261},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10046/}
}
TY - JOUR
AU - Jordan Barrett
AU - Valentino Vito
TI - On Ramsey-minimal infinite graphs
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10046/
DO - 10.37236/10046
ID - 10_37236_10046
ER -
%0 Journal Article
%A Jordan Barrett
%A Valentino Vito
%T On Ramsey-minimal infinite graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10046/
%R 10.37236/10046
%F 10_37236_10046
Jordan Barrett; Valentino Vito. On Ramsey-minimal infinite graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/10046
