Girth and monochromatic copy of trees
Question:
Prove that for every tree $T$ and every integer $g$ there exists a graph $G$ without cycles of length up to $g$ and such that every two-coloring of the edges of $G$ contains a monochromatic copy of $T$.
Thoughts: I saw something similar here https://www.dpmms.cam.ac.uk/~dc340/RamseyLecture5.pdf, but besides the $\mathrm{girth}(G)=g$, I couldn't find a way to connect the information into a start for a proof. Any Hints? (This is similar to this Ramsey (graph) theory question with tree and girth which has no answer)
added after trying to solve using hints in comment:
I have this idea for a proof - Want to verify I got this right as it still seems difficult. I'll use facts 1-4 from here http://how360.org/mathematics/675109/monochromatic-tree .
- From fact 2 we have that exists a graph $G_{g,k}: \delta(G_{g,k})\ge k=|V(T)|$.
- From fact 3 we have that $G_{g,k}$ has a sub-graph H s.t $\delta (H)\ge\frac {|E(G)|}{|V(G)|}\ge k (***)$.
From fact 1 we have that $H$ contains a copy of T.
From fact 4 (pigeonhole) we have that $\frac {|E(G)|}{|V(G)|} \ge \frac {|E(H)|}{|V(G)|} \ge \frac{|E(G)|}{2|V(G)|}$ or $\frac {|E(G)|}{|V(G)|} \ge \frac {|E(G\setminus H)|}{|V(G)|} \ge \frac{|E(G)|}{2|V(G)|}$
- A 2-coloring may be viewed as a partition of G to H (Blue) and H-complement (Red) therefore H or H-complement contains a copy of T - so we have G which has the required girth and it contains a monochromatic copy of T.
The only problem I have now is how to justify the (***) move.
Solution 1:
Filling in the gap (this was asked in the problem (***) and proves item 4 below):
We will write $n(G)$ for $|V(G)|$ and $e(G)$ for $|E(G)|$ and $a(G)$ for $\frac{e(G)}{n(G)}$.
If $G$ does not contain a vertex $v$ with $d(v)<a(G)$, then $\delta(G)\geq a(G)$ and we are done.
Otherwise we produce a graph $G_2$ by removing a vertex $v$ with $d(v)<a(G)$. We get $a(G_2)=\frac{e(G_2)}{n(G_2)}\geq\frac{e(G)-a(G)}{n(G)-1}=a(G)$.
You can repeat this procedure until you arrive at a subgraph $H$ that has $\delta(H)\geq a(H)\geq a(G)$.
ADDED:
I am not sure if your breakdown of the problem is correct, at least I see several problems in it. Here is a breakdown that seems to work.
Find a graph $G$ with girth at least $g$ and minimum degree at least $4k$, where $k=|V(T)|$.
This graph has $\frac{|E(G)|}{|V(G)|}\geq 2k$.
Make an edge-2-coloring. This produces an edge partition $E_1,E_2$ and by symmetry and the pigeonhole principle we may assume that $\frac{|E_1|}{|V(G)|}\geq k$.
In the spanning subgraph of $G$ with edges $E_1$ you can find a subgraph $H$ with $\delta(H)\geq k$.
This subgraph must contain $T$.
ADDED PROOF OF ITEM 1: (For integers $g$ and $k$ there is a graph $G$ with girth at least $g$ and minimum degree at least $k$.)
Let $f(t)=1+k(\sum_{i=0}^t(k-1)^i)$ and take $n>f(2g-1)+kf(g-1)f(2g-1)$.
Construct a graph as follows: start with an empty graph on $n$ vertices, then arbitrarily choose 2 vertices of degree less than $k$ and distance more than $g$ and connect them. Keep doing this until you cannot proceed.
At this moment you have a graph with $n$ vertices, maximum degree $k$ and girth at least $g$.
Now find a vertex $v$ of degree less than $k$ (if there is none, we are done). Note that all vertices of degree less than $k$ must have distance at most $g$ from $v$ (or we would not have stopped our first process), so there are at most $f(g-1)$ vertices of degree less than $k$.
In the same way there are at most $f(2g-1)$ vertices at distance at most $2g$ from $v$. This means that there are at least $kf(g-1)f(2g-1)$ vertices that are further than $g$ away from any low-degree vertex.
We finish the process by iteratively adding edges from a low degree vertex to a far away vertex. Since we need to add at most $kf(g-1)$ edges and since each addition removes at most $f(2g-1)$ far away vertices we have enough far away vertices to make all vertices of degree at least $k$.