On Ramsey-minimal infinite graphs

. 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_{i} n f t y

is an infinite star and

H = n K_{2}

,

n g e 1

is a matching, then the pair

(S_{i} n f t y, n K_{2})

admits no Ramsey-minimal graphs.

Review text

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: On Ramsey-minimal infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656900)