6
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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? $\endgroup$
    – Arnav
    Jul 10 '13 at 21:00
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.