Lesson 3

Theorem (Erdős, 1959). For any sufficiently large number \(k\), there exists a graph \(G_{k}\) with both girth greater than \(k\) and chromatic number greater than \(k\).

Proof. Proof outline:

1. Fix parameters \(n=n(k)\), \(p=p(k)\), \(t=t(k)\), whose values we will choose later.
2. Generate a random graph on \(n\) vertices: include each edge with probability \(p\).
3. Let \(\gamma\) be the number of cycles of length at most \(k\) in \(G\). We will choose parameters so that the inequality \[\operatorname{E}[\gamma] < \frac{n}{4} \ .\] holds. Then, by Markov's inequality, \(\Pr[\gamma \ge \frac{n}{2}] \le \frac{ \operatorname{E}[\gamma]}{n/2}< \frac{1}{2}\).
4. Let \(\beta\) be the number of independent sets of size \(t\). We will choose parameters so that the inequality \[\operatorname{E}[\beta] < \frac{1}{2} \ .\] holds. Again, by Markov's inequality, \(\Pr[\beta \ge 1] \le \frac{ \operatorname{E}[\beta]}{1}< \frac{1}{2}\).
5. From the two probability inequalities, we conclude that there exists a graph \(G\) such that \(\gamma \le \frac{n}{2}\) and \(\beta < 1\), i.e., it has at most \(n/2\) cycles of length at most \(k\) and no independent set of size \(t\).
6. Consider the graph \(G\) and all its cycles of length at most \(k\). We know there are at most \(\frac{n}{2}\) of them. This means we can delete at most \(\frac{n}{2}\) vertices so that no cycles of length at most \(k\) remain. Denote the resulting graph by \(G'\). It has at least \(\frac{n}{2}\) vertices, its girth is greater than \(k\), and the size of any independent set in it is less than \(t\). This gives us a lower bound on the chromatic number of \(G'\) (by the inequality \(\chi(G) \ge \frac{|V|}{\alpha(G)}\)): \[\chi(G') \ge \frac{|V(G')|}{\alpha(G')}\ge \frac{n/2}{t}\ .\] Thus, for \(G'\) to be what we need, we must choose parameters so that the inequality \[n > 2kt \ .\] holds.

Now let's select parameters satisfying the inequalities above. Start with the inequality \(\operatorname{E}[\gamma] < \frac{n}{4}\). \[\operatorname{E}[\gamma]=\sum_{i=3}^{k}\binom{n}{i}\frac{(i-1)!}{2}p^{i} \le \sum_{i=3}^{k}\frac{n^i}{i!}\cdot \frac{(i-1)!}{2}p^{i} \le \sum_{i=3}^{k}(np)^{i} \ .\] Let \(p=n^{\frac{1}{2k}-1}\) (this number is between 0 and 1, so it's valid). Then \(np=n^{\frac{1}{2k}}\), and we obtain a geometric progression that grows asymptotically like its last term, i.e., \((np)^{k}=\sqrt{n}\). So for sufficiently large \(n\), this sum is less than \(\frac{n}{4}\).

Now check the inequality \(\operatorname{E}[\beta] < \frac{1}{2}\): \[\operatorname{E}[\beta]=\binom{n}{t}(1-p)^{\binom{t}{2}}\le \left(\frac{en}{t}\right)^{t} e^{-p\binom{t}{2}}=\left(\frac{en}{t}\cdot e^{-p(t-1)/2}\right)^{t} \ .\] Choose \(t\) so that \(\frac{n}{t}=pt\), i.e., \(t=n^{1-\frac{1}{4k}}\). Then \(\frac{n}{t}=pt=n^{\frac{1}{4k}}\), which grows with \(n\). Then inside the parentheses are factors \(n^{\frac{1}{4k}}\) and \(e^{-n^{\frac{1}{4k}}}\). Clearly, the inverse exponential dominates everything else. (We used the standard inequality \(\binom{n}{t}\le \left(\frac{en}{t}\right)^{t}\), which follows from Stirling’s approximation: \(t! \ge \left( \frac{t}{e} \right)^{t}\), hence \(\binom{n}{t}\le \frac{n^t}{t!}\le \left( \frac{en}{t}\right)^{t}\).)

Finally, to satisfy \(n > 2kt\), just take \(n\) large enough compared to \(k\).◼