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

*

*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}$$?


*Why do we have $
|H|\ge \frac{n}{2}
$ after removing one vertex from each short cycles?
 A: Your understanding of the proof is correct.

*

*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!$$


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

