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

Question

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.

Answer 1

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$.

Answer 2

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$.