One question about the proof of there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest cycle in graph $G$) and $\chi(G)>k$

Question

In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301:

given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest cycle in graph $G$) and $\chi(G)>k$ (the smallest number of colors so that each pair of adjacent vertices with different colors).

The idea of this proof is that we want to find a graph $G$ with fewer 'short' cycles (that is the length at most $k$) and fewer 'big' independent sets (the size of such independent set greater than $n/k$ is called 'big').

Assume that $k\ge 3$. Let the random variable $X(G)$ be the number of short cycles in a random graph $G\in \mathcal{G}(n,p)$. We do expect $X(G)$ is not too large with a high probability.

By the Markov inequality, $$ P(X\ge \frac{n}{2})\le \frac{E[X]}{n/2} $$ where by Lemma 11.1.5 in the textbook, [take $np=n^{\epsilon}\ge 1$, where $p=n^{\epsilon-1}$ and $0<\epsilon<1/k$],

$$E[X]=\sum_{i=3}^kE[X^{(k)}]=\sum_{i=3}^k\frac{(n)_i}{2i}p^i\le \frac{1}{2}(k-2)(np)^k $$ here $E[X^{(k)}]$ is the expected number of $k-$cycles in $G$ and $(n)_i:=n(n-1)\cdots (n-i+1). $

Hence, we upper bound $$ P(X\ge \frac{n}{2})\le (k-2)n^{k\epsilon-1} $$ Since $k\epsilon-1<0$, $\lim_{n\to \infty} P(X\ge \frac{n}{2})=0 $, then take $n$ large enough we have $$ P(X\ge \frac{n}{2})\le \frac{1}{2}. $$

Let $\alpha(G)$ be the largest size of the independent set in $G$. By Lemma 11.2.1 in the textbook, as $n$ large enough and $p=n^{\epsilon-1}$ then $$ P(\alpha(G)\ge \frac{n}{2k})\le \frac{1}{2}. $$

So the event happens with positive probability $$ P(\{X\le \frac{n}{2}\}\cap \{\alpha(G)\le \frac{n}{2k}\})>0 $$

Then we can find a graph $G \in \mathcal{G}(n,p)$ withh fewer than $n/2$ short cycles and $\alpha\le \frac{n}{2k}$ independent vertices.

From each of those cycles delete a vertex, and let $H$ be this graph obtained. Then we have $$ |H|\ge \frac{n}{2} $$ and $H$ has no short cycles. Hence, $g(G)>k$.

Also, by the result in How to prove that $ \chi(G)\alpha(G)\ge |G|? $, we have the chromatic number of $H$ $$ \chi(H)\ge \frac{|H|}{\alpha(H)}\ge k. $$

Do I understand this proof correctly?

---

My questions come from the proof:

1. why can we also find $n$ large enough and $p$ so that $$ P(\alpha(G)\ge \frac{n}{2k})<\frac{1}{2}? $$ The condition in Lemma 11.2.1 is that $p\ge (6k\ln n)n^{-1}$. Does $p=n^{\epsilon -1}$ satisfy this condition? It seems not. We need $$ n^{\epsilon -1}\ge (6k\ln n)n^{-1} $$ and this yields $$\epsilon \ge \frac{ln(6k ln n)}{ln n}$$?

2. Why do we have $ |H|\ge \frac{n}{2} $ after removing one vertex from each short cycles?

Answer 1

Your understanding of the proof is correct.

1. How does $\frac{\ln (6k \ln n)}{\ln n}$ behave when $n$ is large (i.e. when $n$ tends to infinity) ? Do you see why the condition holds ?

For any fixed $\epsilon$, for $n$ large enough, we have $n^\epsilon\gg \ln n$. Therefore $p=n^{\epsilon-1}=\frac{n^\epsilon}{n}\geq \frac{6k\ln n}{n}$

It is important to understand that any polynomial will dominate (i.e be larger) than the $\ln n$ function, as long as $n$ is large enough. And in general keep in mind the following. For fixed $0<\epsilon<1$ and $c>1$, $$ 1\ll \ln\ln n\ll\ln n\ll(\ln n)^c\ll n^\epsilon\ll n\ll n\ln n\ll n^c\ll c^n\ll n!$$

2. In $G$ there are less than $n/2$ short cycles. You can destroy each cycle by removing one vertex. Therefore you can destroy all cycles by removing at most $n/2$ vertices (note that removing one vertex might destroy several short cycles, hence the "at most"). You started with a graph on $n$ vertices, and removed at most $n/2$ vertices, so the graph you get has at least $n/2$ vertices.