Infinite graphs satisfying a certain Ramsey property

84 Views Asked by At

Let $G$ be a countably infinite graph. If $G$ has cliques of arbitrarily large finite size, then $G$ satisfies the following property, which I will call $(*)$: for any $r\in \mathbb{N}$ and any $r$-coloring of the edges of $G$, some triangle must be monochromatic. This is a simple consequence of Ramsey's theorem.

My question is whether the converse is true; namely, if $G$ is a countably infinite graph with property $(*)$, then must $G$ have arbitrarily large cliques?

1

There are 1 best solutions below

3
On BEST ANSWER

For graphs $G,H$ and for $r\in\mathbb N$ let $G\to(H)_r^2$ denote the statement: any $r$-coloring of the edges of $G$ contains a monochromatic subgraph isomorphic to $H$.

Your question is answered in the negative by the Nešetřil-Rödl theorem: for any $r,m\in\mathbb N$ and any $K_m$-free finite graph $H$, there is a $K_m$-free finite graph $G$ such that $G\to(H)_r^2$. In particular, for any $r\in\mathbb N$, there is a $K_4$-free finite graph $G_r$ such that $G_r\to(K_3)_r^2$. The disjoint union of the graphs $G_r$ is a $K_4$-free countable graph $G$ such that $G\to(K_3)_r^2$ for every $r\in\mathbb N$.

Reference: J. Nešetřil and V. Rödl, The Ramsey property for graphs with forbidden complete subgraphs, J. Combinatorial Theory Ser. B 20 (1976), 243-249.