Arbitrary girth and chromatic number

In 1961, using a probabilistic argument, Paul Erdős proved that there exist graphs with arbitrarily large girth and chromatic number. In this blog post, we prove this theorem.

Statement of the theorem

For any number $k\ge 3$, there exists a graph with girth at least $k$ and chromatic number at least $k$.

Idea behind the proof

In a random graph $G\in\mathcal{G}_{n,p}$, as the probability of each edge $p$ increases, so does the expected number of edges in the graph $G$. Increase in the number of edges does two things:

1. It increases the chromatic number $\chi(G)$ of the graph. We want this to prove the theorem.
2. It decreases the girth $g(G)$ of the graph, since more edges mean more chances for a small cycle. We want the opposite of this to prove the theorem.

To get both $\chi(G)\geq{k}$ and $g(G)\geq{k}$, we need a $p$ that is large enough to have the required chromatic number $\chi(G)\geq{k}$, but small enough to have the required girth $g(G)\geq{k}$.

Sketch of the proof

We will implement the above idea as follows:

1. We will construct a random graph $G$ by fixing a value for $p$ such that $G$ has a small number of cycles of length less than $k$, for any large $n$. We will then delete these cycles, giving us a graph $G^\prime$ that has no cycles of length less than $k$. In other words, $g(G^\prime)\geq{k}$. Aha!
2. Keeping $p$ fixed, we will then increase $n$ to get $\chi(G^{\prime\prime})\ge k$. Note that keeping $p$ fixed and increasing $n$ increases the chromatic number of the graph, since $\chi(G^{\prime\prime})\ge v(G^{\prime\prime})/ \alpha(G^{\prime\prime})$ where
• $v(G^{\prime\prime})=O(n)$ (the number of vertices in the graph)
• $\alpha(G^{\prime\prime})=O(\log{n})$ (the maximum size of any color class in the graph).

The interesting thing about this approach is that every graph in the family $\mathcal{G}_{n,p}$ with the above values for $n$ and $p$ will almost surely have both girth and chromatic number $\geq k$.

Techniques used

Probabilistic method

The proof

1. Let $X_i$ be a random variable denoting the number of cycles of length $i$. What is the expected value $E(X_i)$?
1. What is the possible number of cycles of length $i$ over $n$ vertices?
1. Number of ways of choosing $i$ vertices of a cycle: $n \choose i$
2. Number of ways of creating a cycle out of $i$ chosen vertices: $(i-1)!/2$ since any permutation of the $i$ vertices is a cycle. However, cycles have no "ends" (hence the division by $i$) and clock-wise and counter-clock-wise orderings translate to the same cycle (hence the division by 2).
3. So the possible number of cycles of length $i$ over $n$ vertices is $ {n\choose i} (i-1)!/2$.
2. If each edge occurs with probability $p$, then the probability of $i$ edges of the cycle in the graph is $p^i$.
3. So $E(X_i)={n\choose i}(i-1)! p^i/2$
2. Lets call "cycles of length less than $k$" as small cycles.
3. Let $X=\sum_{i=3}^{k-1}X_i$ be a random variable denoting the number of small cycles. What is the expected number of small cycles? $E(X) = E(\sum_{i=3}^{k-1}X_i) = \sum_{i=3}^{k-1}E(X_i) \\ = \sum_{i=3}^{k-1} {n\choose i} (i-1)! p^i/2 \\ \le\sum_{i=0}^{k-1} {n\choose i} (i-1)! p^i/2 \\ \leq \sum_{i=0}^{k-1}(np)^i = \frac{(np)^k-1}{np-1}$
4. What is the probability that the number of such small cycles is more than $n/2$? By Markov's inequality, $\mathbf{Pr}(X>n/2) \le E(X)/(n/2)\le\frac{2(np)^k-1}{n(np-1)}$.
5. By choosing $np=n^{1/k}$, or in other words, $p=p_0:=n^{-(k-1)/k}$ \[\lim_{n\rightarrow\infty}\mathbf{Pr}(X>n/2)=0\] This means that when $p=p_0$, almost surely, we only have small cycles (no large cycles).
6. By deleting one vertex on each of the possibly $n/2$ cycles, we obtain $G^\prime$ which has girth at least $k$. In this process, we would have deleted no more than $n/2$ vertices, meaning the number of vertices in $v(G^\prime)$, $v(G^\prime)\ge n/2$.
7. We have now fixed a value of $p$ for which the graph $G^\prime$ has girth $g(G^\prime)\geq k$. This completes part (1) from the sketch of the proof. Now onto part (2).
8. For $G\in\mathcal{G}_{n,p}$, the size of the maximum independent set $\alpha(G)$ is bounded by $\alpha(G)\leq (1/p)\ln(n^2)$ for large $n$. We also note that deleting vertices does not increase the size of the maximum independent set. This implies that for $G^\prime$, $\alpha(G^\prime)\leq (1/p)\ln(n^2)$ is still valid (where $n$ is the number of vertices in the original graph $G$).
9. The chromatic number for $G^\prime$ \[\chi(G^\prime)\geq v(G^\prime)/\alpha(G^\prime) \geq \frac{(n/2)}{(1/p)\ln(n^2)} = \frac{np}{4\ln(n)} = \frac{n^{1/k}}{4\ln(n)}\] By choosing a large enough $n$, we can get $\chi(G^\prime)\ge k$.

Application

With the above method, for $k=10$, we need a graph $G\in\mathcal{G}_{n,p}$ where $n$ is around $10^{20}$ vertices and probability $p=10^{-18}$. All resulting graphs will almost surely have both girth and chromatic number greater than 10.