On Ramsey-minimal infinite graphs (Q2656900): Difference between revisions

Given graphs \(F\), \(G\) and \(H\), let \(F \to (G, H)\) mean that for any red-blue coloring of the edges of \(F\), there is either a red edge set inducing a copy of \(G\) or a blue edge set inducing a copy of \(H\). This article is concerned with the situation when \(F\) and \(G\) (and possibly \(H\)) are (countably) infinite. It starts with a number of basic results, e.g. if \(G\) and \(H\) are finite and \(F \to (G, H)\), then there is a finite \(F^\prime \subseteq F\) such that \(F^\prime \to (G, H)\). And there is an extension of König's Lemma, as follows. Call a graph `pointed' if it has a distinguished vertex, and call it `locally finite' if each vertex is of finite degree. If \(F\), \(G\), and \(H\) are pointed, let \(F \xrightarrow{\mathrm{poi}} (G, H)\) mean that for any red-blue coloring of \(F\), either there is a red edge set inducing a copy of \(G\) whose distinguished vertex coincides with the distinguished vertex of \(F\), or there is a blue edge set inducing a copy of \(H\) whose distinguished vertex coincides with that of \(F\). If \(F\), \(G\), and \(H\) are pointed, if \(F\) and \(G\) are locally finite, and if \(G\) is connected, then the following is true: if \(F \xrightarrow{\mathrm{poi}} (G^\prime, H)\) for every finite and pointed \(G^\prime \subseteq G\), then \(F \xrightarrow{\mathrm{poi}} (G, H)\). Say that a graph \(F\) is `\((G, H)\)-minimal' if \(F \to (G, H)\) but, for any \(F' \subsetneq F\), \(F^\prime \not\to (G, H)\); for any graphs \(G\) and \(H\), let \({\mathcal R} (G, H)\) be the set of \((G, H)\)-minimal graphs. The primary desideratum appears to be the question: for which \(G\) and \(H\) is \({\mathcal R}(G, H)\) empty? There are several partial results, e.g. this slightly surprising one. Given graphs \(G\) and \(H\), suppose that \(\mathcal F\) is a class of graphs such that \(F \in \mathcal F \implies F \to (G, H)\) and \(F \to (G, H) \implies (\exists F^\prime\subseteq F)(F^\prime \in \mathcal F)\) and for any distinct \(F_1, F_2 \in \mathcal F\), \(F_2 \not\subsetneq F_1\) \& \(F_1 \not\subsetneq F_2\); then \(\mathcal R(G, H)\) is the class of all \(F \in \mathcal F\) such that \(F\) is not isomorphic to any proper subgraph of itself. The article concludes with a number of more involved examples, including some in which \(G\) may be an infinite comb graph and some in which \(H\) is a finite matching.