# Is there a graph that is Ramsey for $P_{2n}$ but is $C_{2n+1}-$free

Write $F\to G$ to mean that for every two coloring of the edges of $F$, there exists a monochromatic copy of $G$. Nešetřil and Rödl proved that for every graph $G$, there exists a graph $F$ such that $F\to G$ and $\omega (F)=\omega (G)$ (where $\omega$ is the size of the largest clique in the graph).

My question is an extension of that. Is there a graph $F$ so that $F \to P_{2n}$ but so $F$ is $C_{2n+1}-$free? This is trivial for $n=1$. For $n=2$, the graph $F:= C_6\cup \{(x,v_i)|i=1,3,5\}$ works (where $v_1,\dots,v_6$ are the vertices of the $C_6$ and $x\not \in C_6$).

The motivation is that if this is true, I can construct another graph with a special property (using this lemma) that will help me solve a much more interesting problem (depending on how interesting this itself is!)

So my question is, does this generalize to all $n$? It seems that it should.

• Actually, I think this paper should solve it: math.mit.edu/~fox/paper-foxlin.pdf In 3.2, they construct a bipartite graph $B$ so that $B \to K_{2n+1,2n+1}$. But $K_{2n+1,2n+1}$ has a $P_{2n}$ in it, and since $B$ is bipartite it doesn't even have a $C_3$. Is this a correct proof? Jul 10 '13 at 21:00

Taking $F=K_{4n, 4n}$ does the trick. To see this, suppose we have coloured each edge of $K_{4n,4n}$ red or blue. Let $R$ and $B$ be the red and blue subgraphs of $K_{4n,4n}$. We may assume that $R$ contains at least $8n^2$ edges. Hence, the average degree of $R$ is at least $2n$. Thus, $R$ contains an induced subgraph $R'$ with minimum degree at least $n$, and so $R'$ evidently contains a path of length $n$.
A simple proof of much more: for each $n$ and $g$, there is a graph $G$ with girth at least $g$ that is Ramsey for $P_n$. As shown by Erdos, there are graphs of arbitrarily large girth and chromatic number. Let $G$ be a graph with girth at least $g$ and chromatic number at least $4n+1$, so it contains a subgraph of minimum degree at least $4n$. Any two-coloring of the edges of $G$ thus contains a monochromatic subgraph of average degree at least $2n$ and hence a subgraph of minimum degree at least $n$. One can then greedily build a monochromatic path of length $n$, showing that $G$ is Ramsey for $P_n$.