Choosing Parameters for Girth and Chromatic Growth

The Parameter-Choice Problem

To construct a graph with large girth and large chromatic number, two competing requirements must be met. The graph should contain few cycles below the desired girth, so that deleting vertices can remove them at a small cost. At the same time, its independent sets should be small: after deletion, this forces many color classes. The useful choice of edge probability lies between these requirements.

Fix an integer \(g\ge 3\). For an integer \(n\ge 1\) and a real number \(p\in[0,1]\), let \(G(n,p)\) be the random simple graph with vertex set \(\{1,\ldots,n\}\), in which each possible edge is included independently with probability \(p\). Write \(Y\) for the number of cycles of lengths \(3,4,\ldots,g-1\), and \(X_k\) for the number of independent vertex sets of size \(k\). An independent set is a set containing no adjacent pair of vertices. The girth is the length of a shortest cycle, and is taken to be infinite when the graph has no cycles.

Here \(o(n)\) means a quantity whose ratio to \(n\) tends to zero as \(n\) tends to infinity. The principle describes the balance; the estimates below give a specific safe choice and prove that the construction works.

Estimating the Short Cycles

For each \(j\ge 3\), the number of possible cycles of length \(j\) on \(n\) labelled vertices is \((n)_j/(2j)\), where \((n)_j=n(n-1)\cdots(n-j+1)\). Each such cycle appears in \(G(n,p)\) exactly when its \(j\) edges are all present, an event of probability \(p^j\). By linearity of expectation, the expected number \(Y_j\) of \(j\)-cycles therefore satisfies

Summing this bound over the finitely many lengths below \(g\) is the key: if \(np=n^\varepsilon\), the largest power in the sum is \(n^{(g-1)\varepsilon}\). This is sublinear precisely when \((g-1)\varepsilon<1\). For \(g=3\), there are no cycle lengths to remove, so \(Y=0\) without any estimate.

Estimating Independent Sets

For a fixed set of \(k\) vertices to be independent, all \(\binom{k}{2}\) possible edges within it must be absent. This has probability \((1-p)^{\binom{k}{2}}\). Summing the indicator variables of the \(k\)-vertex sets gives

The inequality uses \(\binom{n}{k}\le(en/k)^k\) and \(1-p\le e^{-p}\). If \(\mathbb{E}X_k<1\), the probability that \(X_k\ge1\) is less than \(1\), so some graph has no independent \(k\)-set. The next choice makes the expectation much smaller than \(1\).

A Complete Choice and Its Guarantee

We now fix the convenient exponent \(\varepsilon=1/(2g)\), giving \(p=n^{-1+1/(2g)}\). The strict inequality \( (g-1)/(2g)<1\) ensures that the short-cycle expectation is sublinear. Let \(k=\lceil8\ln n/p\rceil\). For sufficiently large \(n\), \(k\le n\), because

For the cycle estimate, when \(g\ge4\), there are \(g-3\) possible lengths \(j=3,\ldots,g-1\). Since \(np=n^{1/(2g)}\), each term is at most \(n^{(g-1)/(2g)}\), and so

For \(g=3\), \(Y=0\). In every case, take \(n\) sufficiently large that \(\mathbb{E}Y<n/8\). The independent-set calculation also applies: for \(n\ge3\), \(p(k-1)\ge8\ln n-p\ge7\ln n\), and \(\ln(en/k)\le2\ln n\) whenever \(k\le n\). Therefore \(\mathbb{E}X_k\le\exp(-3k\ln n/2)<1/4\).

Proof. Choose \(n\) large enough to satisfy all the preceding bounds, and sample \(G(n,p)\) with \(p=n^{-1+1/(2g)}\). For a nonnegative random variable \(Z\) and \(a>0\), Markov's inequality gives \(\Pr(Z\ge a)\le\mathbb{E}Z/a\). Applying it to \(Y\) gives \(\Pr(Y\ge n/2)\le2\mathbb{E}Y/n<1/4\). Also, \(\Pr(X_k\ge1)\le\mathbb{E}X_k<1/4\), since \(X_k\) is a nonnegative integer. The union bound shows that the probability either event occurs is less than \(1/2\). Thus some sampled graph has \(Y<n/2\) and \(X_k=0\).

In that graph, select one vertex from each cycle of length less than \(g\) and delete the selected vertices. At most \(Y<n/2\) vertices are deleted. Every original cycle of length less than \(g\) contains its selected vertex, so none remains; deleting vertices cannot create a new cycle. The resulting graph \(H\) therefore has girth at least \(g\) and more than \(n/2\) vertices. Since \(X_k=0\), the original graph has no independent set of size \(k\), and neither does its induced subgraph \(H\). Each color class in a proper coloring is independent, so \(|V(H)|\le\chi(H)(k-1)\). In particular, \(\chi(H)>n/(2k)\), using \(|V(H)|>n/2\) and \(k-1<k\). Finally, \(k\le8n^{1-1/(2g)}\ln n+1\), so \(n/(2k)\) tends to infinity as \(n\) grows. Choosing \(n\) still larger makes \(\chi(H)>M\). \(\square\)

What the Parameter Range Is Doing

There is a second constraint: \(\varepsilon\) must be positive. With \(p=n^{-1+\varepsilon}\), the scale of the chromatic lower bound is \(np/\ln n=n^\varepsilon/\ln n\). If \(\varepsilon=0\), then \(p=1/n\) and this scale is \(1/\ln n\), which tends to zero rather than infinity. A sparse graph may have few short cycles, but that alone does not force a large chromatic number.

Common Pitfall: Checking Only One Requirement

A tempting but incomplete choice is \(p=1/n\). Indeed, \(np=1\), so the expected number of cycles of any fixed length \(j\) is at most \(1/(2j)\), a bounded quantity. But the independent-set argument with \(k=\lceil8\ln n/p\rceil\) gives \(k=\lceil8n\ln n\rceil>n\) for \(n\ge3\). It supplies no useful small-independent-set conclusion: there cannot be a set of more than \(n\) vertices at all. The correction is to choose a fixed positive \(\varepsilon\) below \(1/(g-1)\). Then short cycles still have sublinear expected count, while \(np=n^\varepsilon\) makes the chromatic lower-bound scale \(n^\varepsilon/\ln n\) grow without bound.

The key is not merely to make cycles rare or independent sets small in isolation. The probability \(p\) must make both estimates useful at once, and the vertex deletion must be charged against the same graph for which the independent-set bound holds. The positive-probability argument in the proof ensures that these two properties occur together.