On Ramsey-minimal infinite graphs

(i) Suppose that $V=\{v_{1},\ldots,v_{n}\}$ and that $H=G-\{v_{1},\ldots,v_{n-1}\}$ contains $G$. In other words, there is a subgraph $G^{\prime}\subseteq H$ isomorphic to $G$. Since $G^{\prime}$ and $G$ are isomorphic, $G^{\prime}$ is strongly self-embeddable. Thus, $G^{\prime}-v_{n}$ must contain $G^{\prime}\cong G$. Since $G^{\prime}-v_{n}\subseteq H-v_{n}=G-V$, we can conclude that $G-v$ contains $G$.

(ii) Suppose that $e=uv$. Since $G-v$ contains a copy of $G$ by hypothesis, we have that $G-e\supseteq G-v$ contains $G$ as well. The statement for any $G-E$ then follows by induction. ∎

Let $X$ be the product of $|E(F)|$-many copies of the discrete space $S=\{\text{red},\text{blue}\}$, equipped with the product topology. We can identify $X$ with the set of all functions $E(F)\to S$, i.e. the set of all red-blue colorings of $F$’s edges. By Tychonoff’s theorem, $X$ is compact.

By assumption, $F\to(G,H)$, so for every coloring $c\in X$, we can pick a finite set of edges $D_{c}$ forming either a red $G$ or a blue $H$. Then, each $c|_{D_{c}}$ determines a basic open set

Since $c\in O_{c}$ for all $c\in X$, the collection $\{O_{c}:c\in X\}$ covers $X$. By compactness, there is a finite sequence $c_{1},\ldots,c_{n}\in X$ so that $O_{c_{1}}\cup\cdots\cup O_{c_{n}}=X$.

Let $\hat{F}$ be the subgraph of $F$ induced by $D_{c_{1}}\cup\cdots\cup D_{c_{n}}$. We claim $\hat{F}\to(G,H)$. Pick a coloring $\hat{d}\colon E(\hat{F})\to S$, and extend it arbitrarily to a coloring $d\colon E(F)\to S$. Then, there is an $i\leqslant n$ such that $d\in O_{c_{i}}$, so $D_{c_{i}}\subseteq E(\hat{F})$ either forms a red $G$ or a blue $H$ under $\hat{d}$, as required. ∎

Since $G$ is locally finite and connected, it must be countable (see Exercise 1, Chapter 8 of [7]). The lemma clearly holds if $G$ is finite, so assume that $G$ is countably infinite. Enumerate $V(G)$ as follows: let $v_{0}=*$, let $v_{1},\ldots,v_{k}$ be the neighbors of $*$, let $v_{k+1},\ldots,v_{\ell}$ be the vertices of distance 2 to $*$, etc. This indeed enumerates $G$ by the assumption that $G$ is locally finite and connected. Then, the induced subgraphs $\hat{G}_{n}:=G[v_{0},\ldots,v_{n}]$ are all connected, finite, pointed subgraphs of $G$.

For each $n$, let $V_{n}$ be the set of pointed embeddings $\hat{G}_{n}\hookrightarrow F$. Each $V_{n}$ is nonempty by assumption. Inductively, we show each $V_{n}$ is finite. We see that $V_{0}$ is finite, since there is a unique embedding $\hat{G}_{0}\hookrightarrow F$ mapping $*_{G}$ to $*_{F}$. Now assume $V_{n}$ is finite, and pick $f\in V_{n}$. Since $\hat{G}_{n+1}$ is connected, $v_{n+1}$ is adjacent to some $v_{j}$ for $j\leqslant n$. Since $F$ is locally finite, $f(v_{j})$ has finite degree, so there are only finitely many ways to define $f(v_{n+1})$ and extend $f$ to an embedding in $V_{n+1}$. Since there are also only finitely many ways to choose $f\in V_{n}$, it follows that $V_{n+1}$ is finite, and so all the $V_{n}$ are finite by induction.

Similarly to before, let $K$ be the graph on $\bigcup_{n=0}^{\infty}V_{n}$, where we insert all edges between $f\in V_{n+1}$ and $f|_{\hat{G}_{n}}\in V_{n}$. By Lemma 6, $K$ contains an infinite ray $f_{0}f_{1}\ldots$ such that $f_{n}\in V_{n}$ for all $n$. Define $f\colon V(G)\to V(F)$ by $f(v_{n})=f_{n}(v_{n})$. We claim $f$ is a pointed embedding $G\hookrightarrow F$.

1. (i)

   $f$ is a graph homomorphism: suppose $v_{n}v_{m}\in E(G)$, where $n\leqslant m$. We have $f(v_{n})=f_{n}(v_{n})=f_{m}(v_{n})$ and $f(v_{m})=f_{m}(v_{m})$. Since $f_{m}$ is a graph homomorphism, $f(v_{n})f(v_{m})=f_{m}(v_{n})f_{m}(v_{m})\in E(F)$.

2. (ii)

   $f$ is injective: suppose $f(v_{n})=f(v_{m})$ for $n\leqslant m$. Then, $f_{m}(v_{n})=f_{n}(v_{n})=f_{m}(v_{m})\implies v_{n}=v_{m}$ since $f_{m}$ is injective.

3. (iii)

   $f$ is pointed: $f(*_{G})=f_{0}(*_{G})=*_{F}$ since $f_{0}$ is pointed.∎

Pick an arbitrary basepoint $*\in F$. For every $n$, we claim that $P_{n}$ (with $*_{P_{n}}$ chosen as an endpoint) admits a pointed embedding into $F$. If $P_{n}$ does not admit a pointed embedding into $F$, then there is no vertex $v\in V(F)$ such that $d(*_{F},v)\geqslant n$. Since $F$ is connected and locally finite, we can enumerate $V(F)$ as follows: let $v_{0}=*$, let $v_{1},\ldots,v_{k}$ be the neighbors of $*$, let $v_{k+1},\ldots,v_{\ell}$ be the vertices of distance 2 to $*$, etc. By stage $n$, we will have enumerated all of $F$, hence $F$ is finite; contradiction. The result now follows from Proposition 7, with $G=P_{\infty}$ and $*_{P_{\infty}}$ as its endpoint. ∎

Take an arbitrary red-blue coloring of $F$ such that $F$ does not contain a blue $H$. Denote $F^{\prime}$ as the pointed subgraph of $F$ induced by all the red edges. By assumption, all connected, finite, pointed $\hat{G}\subseteq G$ admits a pointed embedding into $F^{\prime}$. By Proposition 7, $G$ admits a pointed embedding into $F^{\prime}$, so a red $G$ exists as a pointed subgraph of $F$. ∎

(i) Fix a $(G,H)$-minimal graph $\Gamma$. By condition (2), there is an $F\in\mathcal{F}$ such that $F$ is contained in $\Gamma$. Since $F\to(G,H)$ by condition (1), we must have $F=\Gamma$ as $\Gamma$ is $(G,H)$-minimal. Therefore, $\Gamma\in\mathcal{F}$. By Observation 2, $\Gamma$ is not self-embeddable, and we are done.

(ii) follows directly from (i). ∎

(i) We prove that $\{F\in\mathcal{F}:\text{$F$ is not self-embeddable}\}\subseteq\mathcal{R}(G,H)$. Suppose $F\in\mathcal{F}$ is not self-embeddable. Since $F\to(G,H)$ by condition (1), it remains to show that no proper $F^{\prime}\subset F$ arrows $(G,H)$. If we assume the contrary, then we have an $F^{\prime\prime}\in\mathcal{F}$ contained in $F^{\prime}$ by condition (2). This implies that $F$ contains $F^{\prime\prime}$ and contradicts condition (3).

(ii) follows easily from (i). ∎

(i) Take $\mathcal{F}=\{G\}$. Conditions (1)–(3) of Theorems 10 and 11 all hold when $H=K_{2}$. The statement directly follows from Theorem 11.

(ii) Again, take $\mathcal{F}=\{G\}$. Conditions (1) and (2) of Theorem 10 are both satisfied. Now we just need to show that $G$ is self-embeddable. Color an arbitrary edge of $G$ blue and the rest of the edges red. Since $H\neq K_{2}$, there is no blue $H$ in $G$. So by the fact that $G\to(G,H)$, there is a red copy of $G$ in $G$. This proves that $G$ properly contains itself, and thus self-embeddable. ∎

(i) Fix a red-blue coloring of $nG$ which does not create a blue $nK_{2}$. It follows that there must be a component of $nG$ isomorphic to $G$ which is colored all red. Hence, $nG\to(G,nK_{2})$.

Now let $e\in E(nG)$ be an arbitrary edge located in some component $G^{\prime}$ of $nG$. We show that $nG-e\not\to(G,nK_{2})$ by constructing a $(G,nK_{2})$-good coloring of $nG-e$ as follows: for every component of $nG$ other than $G^{\prime}$, color one of its edges blue; color the rest of the edges red. Since $G$ is connected, there are exactly $n-1$ components in $nG$ other than $G^{\prime}$, so this coloring only manages to produce a blue $(n-1)K_{2}$. Also, since $G$ is not self-embeddable, there cannot be a red $G$ in any of the components of $nG$. By the connectivity of $G$, there cannot be a red $G$ in all of $nG$ either. Therefore, this coloring is indeed $(G,nK_{2})$-good.

(ii) By appealing to Theorem 12(ii), it suffices to prove that $G\to(G,nK_{2})$. Fix a red-blue coloring of $G$ which does not create a blue $nK_{2}$. We claim that this coloring creates a red $G$. We construct a set of vertices $V\subset V(G)$ using the following algorithm:

1. 1.

   initialize $V=\emptyset$

2. 2.

   while $G-V$ contains a blue edge do

3. 3.

   choose a blue edge $e=uv$ in $G-V$

4. 4.

   $V\leftarrow V\cup\{u,v\}$

5. 5.

   output $V$

This algorithm must terminate after at most $n-1$ while loop iterations since the edge chosen at each iteration must be independent from the edges chosen at previous iterations. It is then clear that the output $V$ is finite and that $G-V$ only contains red edges. By Proposition 4(i), we have a copy of $G$ in $G-V$. It follows that there exists a red copy of $G$ in $G$, and we are done. ∎

To prove condition (1), we show that $F\to(S_{\infty},nK_{2})$ for all $F\in\mathcal{F}_{n}$ by induction on $n$. The base case $n=1$ follows from the fact that $\mathcal{F}_{1}=\{S_{\infty}\}$ and $S_{\infty}\to(S_{\infty},K_{2})$. Now assume that every graph in $\mathcal{F}_{n}$ arrows $(S_{\infty},nK_{2})$, and let $F\in\mathcal{F}_{n+1}$ be arbitrary. Suppose that $c$ is a red-blue coloring of $F$ which produces no red $S_{\infty}$.

Pick an arbitrary vertex $u$ adjacent to $x_{n+1}\in X$ such that $u\notin X$ and the edge $x_{n+1}u$ is colored blue. This can be done since otherwise, $x_{n+1}$ is incident to infinitely many red edges. Observe that $F^{\prime}:=F-\{x_{n+1},u\}$ is an element of $\mathcal{F}_{n}$, so it contains a blue $nK_{2}$ with respect to the coloring $c|_{F^{\prime}}$. Since this blue $nK_{2}$ and the blue $x_{n+1}u$ form an independent set of edges, there exists a blue $(n+1)K_{2}$ in $F$ with respect to $c$. This proves that $F\to(S_{\infty},(n+1)K_{2})$ and completes the induction.

Now we prove condition (2). Suppose that $\Gamma$ arrows $(S_{\infty},nK_{2})$. We claim that $\Gamma$ contains at least $n$ vertices of infinite degree. Assume that $Y$, where $|Y|<n$, is the set of vertices of $\Gamma$ having an infinite degree. By coloring all edges incident to a vertex in $Y$ blue and the rest of the edges red, we obtain a $(S_{\infty},nK_{2})$-good coloring of $\Gamma$; contradiction. Now, we can take arbitrary vertices $x_{1},\ldots,x_{n}$ of $\Gamma$ of infinite degree. The subgraph of $\Gamma$ induced by all edges that are incident to at least one of $x_{1},\ldots,x_{n}$ is an element of $\mathcal{F}_{n}$, therefore condition (2) holds. ∎

Let $n\geqslant 1$. Take $\mathcal{F}_{n}$ as defined in Lemma 20. Invoking Theorem 10(ii), we need to show that every $F\in\mathcal{F}_{n}$ is self-embeddable.

Let $F\in\mathcal{F}_{n}$ be arbitrary. We aim to define a nontrivial self-embedding $\varphi$ of $F$. Denote $U$ as the complement of $X$ (i.e. $U:=V(F)\setminus X$), and for all $1\leqslant i\leqslant n$, let $\rho_{i}\colon U\to\{0,1\}$ be such that $\rho_{i}(u)=1$ iff $u$ is adjacent to $x_{i}$. Define $\rho(u)=(\rho_{1}(u),\ldots,\rho_{n}(u))$ for every $u\in U$. Since the image of $\rho$ is finite, then by the infinite pigeonhole principle, there exists an $x\in\{0,1\}^{n}$ such that $\rho^{-1}(x)$ is an infinite set, say $\rho^{-1}(x)=\{u_{1},u_{2},\ldots\}$. Define $\varphi\colon V(F)\to V(F)$ as

It is clear that $\varphi$ is injective, and it is nontrivial since $u_{1}\notin\varphi(V(F))$. It remains to show that $\varphi$ is a graph homomorphism. Suppose that $uv\in E(F)$. By condition (b), we can assume without loss of generality that $v\in X$, say $v=x_{j}$ for some $1\leqslant j\leqslant n$. Since $v\notin U$, we must have $v\notin\rho^{-1}(x)$, so $\varphi(v)=v$. If $u\notin\rho^{-1}(x)$, then $\varphi(u)\varphi(v)=uv\in E(F)$, and we are done. So assume that $u=u_{i}$ for some $i\geqslant 1$. Since $uv=u_{i}x_{j}$ is an edge, we have that $\rho_{j}(u_{i})=1$. Thus, we also have $\rho_{j}(u_{i+1})=1$ since $\rho(u_{i+1})=x=\rho(u_{i})$. It follows that

The proof that $\varphi$ is a nontrivial self-embedding is then complete. ∎

Implication $(1\to 2)$ is trivial, while implications $(2\to 3)$ and $(4\to 1)$ are both consequences of Theorem 16. So we just need to prove $(5\to 4)$ and $(3\to 5)$.

$5\to 4$: Let $v\in V(C^{\ell})$. If $v=x_{0}$, then by positively translating $C^{\ell}$ by $p$ (so that $x_{n}\mapsto x_{n+p}$ and $P_{\ell(n)}$ maps into $P_{\ell(n+p)}$), we obtain an embedding $C^{\ell}\hookrightarrow C^{\ell}-v$. Otherwise, there exists a $k\in\mathbb{N}$ such that $v$ is located in the path $P_{\ell(k)}$ attached to $x_{k}$. In this case, positively translate $C^{\ell}$ by $ap$, where $a$ is chosen such that $ap>k$, to obtain the desired embedding into $C^{\ell}-v$.

$3\to 5$: Let $\varphi\colon V(C^{\ell})\to V(C^{\ell})$ be a nontrivial self-embedding given by the assumption that $C^{\ell}$ is self-embeddable. We cannot have $\varphi(x_{0})=x_{0}$, since that would mean $\varphi$ is the identity map, hence not nontrivial. Thus, $\varphi(x_{0})$ is located in the path $P_{\ell(k)}$, which is attached to $x_{k}$, for some $k\in\mathbb{N}$. Suppose that $P_{\ell(k)}:=x_{k}y_{1}\ldots y_{\ell(k)-1}$.

If $\varphi(x_{0})=x_{k}$, then $\varphi$ must be a positive translation by $k$. Hence, statement 5 holds by taking $p=k$ since $\varphi$ maps each $P_{\ell(n)}$ into $P_{\ell(n+k)}$. So assume that $\varphi(x_{0})=y_{j}$ for some $1\leqslant j\leqslant\ell(k)-1$. This has an implication that $\ell(k)>1$, and thus $s\leqslant k$ since $s=\min_{\ell(n)>1}n$. Observe that we cannot have $j>s$ since that would mean $\varphi(x_{s})=y_{j-s}$ has degree $2$, which is less than $\deg(x_{s})=3$; contradiction. In summary, we have the inequality $j\leqslant s\leqslant k$.

We claim that $j<k$. Assume for the sake of contradiction that $j=s=k$. Since we have established that $j\leqslant\ell(k)-1$ and $s\geqslant\ell(s)-1=\ell(k)-1$, we then have $\ell(k)-1=j=s=k$. It follows that $\varphi$ must be the map