Ravi is an armchair futurist and an aspiring mad scientist. His mission is to create simplicity out of complexity and order out of chaos.

## Thursday, May 23, 2013

### 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$.

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

#### 1 comment:

1. This comment has been removed by a blog administrator.