Theorem11.7Erdős
For every pair \(g,t\) of integers with \(g\ge3\text{,}\) there exists a graph \(G\) with \(\chi(G)>t\) and the girth of \(G\) greater than \(g\text{.}\)
At the outset of this chapter, we presented Erdős' original proof for the lower bound for the Ramsey number \(R(n,n)\) using counting. Later, we recast the proof in a probabilistic setting. History has shown that this second perspective is the right one. To illustrate the power of this approach, we present a classic theorem, which is also due to Erdős, showing that there are graphs with large girth and large chromatic number.
The girth \(g\) of a graph \(G\) is the smallest integer for which \(G\) contains a cycle on \(g\) vertices. The girth of a forest is taken to be infinite, while the girth of a graph is three if and only if it has a triangle. You can check the families of triangle-free, large chromatic number, graphs constructed in Chapter 5 and see that each has girth four.
For every pair \(g,t\) of integers with \(g\ge3\text{,}\) there exists a graph \(G\) with \(\chi(G)>t\) and the girth of \(G\) greater than \(g\text{.}\)
Experienced researchers are able to simplify the calculations in an argument of this type, as they know what can safely be discarded and what can not. Here's a quick tour of the essential steps. We want \(E(X_1)\) to be small, so we set \(n^se^{-ps^2}=1\) and get \(s=\ln n/p\text{.}\) We want the number of small cycles to be about \(n\) so we set \((gp)^g=n\) and get \(p=n^{1/g-1}\text{.}\) Finally, we want \(n=st\) which requires \(n^{1/g}=t\text{.}\) The rest is just paying attention to details.