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:- It increases the chromatic number $\chi(G)$ of the graph. We want this to prove the theorem.
- 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:- 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!
- 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
The proof
- Let $X_i$ be a random variable denoting the number of cycles of length $i$. What is the expected value $E(X_i)$?
- What is the possible number of cycles of length $i$ over $n$ vertices?
- Number of ways of choosing $i$ vertices of a cycle: $n \choose i$
- 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).
- So the possible number of cycles of length $i$ over $n$ vertices is $ {n\choose i} (i-1)!/2$.
- If each edge occurs with probability $p$, then the probability of $i$ edges of the cycle in the graph is $p^i$.
- So $E(X_i)={n\choose i}(i-1)! p^i/2$
- Lets call "cycles of length less than $k$" as small cycles.
- 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}$
- 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)}$.
- 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).
- 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$.
- 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).
- 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$).
- 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.