Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 12 (Extremal Graph Theory)

Write $K_s(t)$ for the balanced graph blow-up of a complete graph, with $s$ classes of size $t$; containment here is as a subgraph, not necessarily an induced subgraph. The logarithmic form of the Erdős-Stone theorem is: for fixed $r\ge 1$ and $0<ϵ<1/r$, there are $d=d(r,ϵ)>0$ and $n_0$ such thatThus the guaranteed balanced part size is at least $\lfloor d\log n\rfloor$, with $d$ independent of $n$. We prove the logarithmic Erdős-Stone theorem by a density-to-cliques step and a constructive dense clique family blow-up lemma.

First choose a fixed $m$ large enough that $t_r(m)/\left(\genfrac{}{}{0ex}{}{m}{2}\right)\le 1-1/r+ϵ/2$, where $t_r(m)$ is the edge count of the Turan graph. A uniformly chosen $m$-vertex subset has expected edge count at least $(1-1/r+ϵ)\left(\genfrac{}{}{0ex}{}{m}{2}\right)$. If its induced graph contains no $K_{r+1}$, the Turan theorem bounds that count by $t_r(m)$. Since the count is always at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, the probability that the subset contains an $(r+1)$-clique is at least $ϵ/2$. Double counting the incidences between such subsets and their cliques gives, for $s=r+1$,for a fixed $\eta >0$ and all sufficiently large $n$. Here $(x{)}_s=x(x-1)\cdots (x-s+1)$. This is clique supersaturation by sampling.

We now prove the needed dense clique family blow-up lemma, with the following stronger induction invariant. Given any family $\mathcal{M}$ of at least $\eta n^s$ distinct $s$-cliques, there is a complete $s$-partite subgraph with each class of size $\lfloor a_s(\eta )\log n\rfloor$, containing that many pairwise vertex-disjoint transversal members of $\mathcal{M}$, each with one vertex in every class. Extra edges within its classes can be ignored. We may suppose $0<\eta <1/2$. For $s=1$, any $\eta n$ singletons suffice, and we may take $a_1(\eta )=1$ once $n$ is large.

For $s\ge 2$, put $\theta =\eta /2$. Repeatedly delete every member of the current family containing an $(s-1)$-clique whose number of extensions is at most $\theta n$. Each such face is processed at most once, and there are at most $n^{s-1}$ possible faces. At most $\theta n^s$ members are deleted. The remaining family $\mathcal{L}$ has size at least $(\eta /2)n^s$, and every face that remains has more than $\theta n$ extensions. Its family of $(s-1)$-faces has size at least $s|\mathcal{L}|/n\ge (\eta /2)n^{s-1}$, since each face is in at most $n$ members.

Apply the induction hypothesis to these faces. It gives a complete $(s-1)$-partite subgraph with $m=\lfloor a_{s-1}(\eta /2)\log n\rfloor$ vertices in each class and a matching $R_1,\dots ,R_m$ of transversal $(s-1)$-faces from the family. Form a bipartite graph whose left vertices are the $R_i$ and whose right vertices are the original $n$ vertices; join $R_i$ to $v$ when $R_i\cup \{v\}\in \mathcal{L}$. Every left degree exceeds $\theta n$.

The following common neighbourhood from bipartite density estimate is elementary. In a bipartite graph with class sizes $m,n$ and at least $\theta mn$ edges, averaging over left subsets $S$ of size $u$ and using convexity of the integer sequence $j\mapsto \left(\genfrac{}{}{0ex}{}{j}{u}\right)$ giveswhenever $1\le u\le \theta m/2$. The last inequality follows by comparing the $u$ factors in the two binomial coefficients; the integer convexity follows from the nondecreasing first differences $\left(\genfrac{}{}{0ex}{}{j}{u-1}\right)$.

ChooseFor large $n$, $m\ge \frac{1}{2}{a}_{s-1}(\eta /2)\log n$, so $u\le \theta m/4$. The estimate supplies $u$ selected faces with a common extension set of size at least $n(\theta /2{)}^u\ge \sqrt{n}$. This extension set is disjoint from the selected faces: a vertex in any one of them cannot extend that face. Their union has $u$ vertices in each of the old $s-1$ classes, with all required cross edges; choose $u$ distinct common extension vertices as a new class. Attaching one different extension vertex to each selected face also gives $u$ disjoint members of $\mathcal{L}$. This completes the induction, with positive constants independent of $n$. Apply it to the clique family above and take $d=a_{r+1}(\eta )$.

The logarithmic order cannot be increased in a uniform forcing result. Put $\rho =1-1/r+ϵ<1$, choose $p$ strictly between $\rho$ and one, and take a binomial random graph. Its edge density exceeds $\rho$ with probability tending to one, by the variance estimate for a sum of independent edge indicators. With $s=r+1$, the expected number of ordered embeddings of $K_s(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/((s-1)\log (1/p))$, the logarithm of this bound is negative of order $(\log n{)}^2$. Markov's inequality therefore makes the probability of any such copy tend to zero. Both events hold simultaneously for some graphs of every sufficiently large order. There are graphs meeting the density hypothesis whose largest balanced blow-up has part size $O(\log n)$. This upper bound concerns what density can force; it is not an upper bound for every dense graph, since a complete graph has much larger blow-ups.

Finally, $H_k$ is the square of a cycle, for $k\ge 3$. Any three consecutive vertices form a triangle in a graph. In a proper three-colouring, once the first three colours are fixed, each subsequent vertex must repeat the colour three positions earlier. Closing the cycle is possible precisely when $3\mid k$. Conversely, repeating the three colours gives such a colouring whenever $3\mid k$. In that case $H_k$ embeds in $K_3(k/3)$, and the density $0.51\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ exceeds the bipartite Turan theorem threshold by a fixed amount, so the theorem forces $H_k$ eventually. If $3\nmid k$, the balanced Turan graphs $T_3(n)$ have density at least $2/3$ and contain no graph of chromatic number greater than three. They give a counterexample sequence. Exactly the cycle lengths $k\ge 3$ divisible by three have the required property.

For a fixed uniform hypergraph $H$ with $h$ vertices, uniformity $\ell$, and at least one edge, define its Turán density bywhere $\mathrm{ex}(n,H)$ is the maximum edge count of an $H$-free hypergraph. The limit exists: averaging the edge count over all $m$-vertex subsets of an extremal $n$-vertex hypergraph, with $n\ge m\ge \ell$, shows that the displayed normalized extremal numbers are nonincreasing. Thus their limit is their infimum.

For hypergraph supersaturation by sampling, choose $m\ge h$ so that $\mathrm{ex}(m,H)/\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)\le \pi (H)+ϵ/2$. The expected edge count in a uniform $m$-vertex subset of $G$ is at least $(\pi (H)+ϵ)\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$. A subset containing no copy of $H$ has at most $(\pi (H)+ϵ/2)\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$ edges, while any subset has at most $\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$. Hence at least an $ϵ/2$ fraction of the subsets contain $H$. Every particular copy of $H$ lies in exactly $\left(\genfrac{}{}{0ex}{}{n-h}{m-h}\right)$ such subsets, so their number is at leastfor $n\ge N=\max (m,2h)$. TakeFor $n<N$, the requested integer lower bound is zero; for $n\ge N$, the calculation proves it. This positive $\delta$ depends only on $H$ and $ϵ$. If the density hypothesis is impossible there is nothing to prove. For an edgeless $H$, every $h$-set is already a copy and the conclusion follows directly.

For the edge-triangle objective, let $N(v)$ be the open neighbourhood of $v$ and define its local scoreIt counts the contribution to $k_2-c{k}_3$ of edges and triangles in a graph containing $v$. If $u,v$ are nonadjacent, making $u$ a false twin of $v$ changes the objective by $s(v)-s(u)$, since no edge or triangle in a graph uses both. More generally, partition vertices into false-twin classes, meaning equal open neighbourhoods. If distinct classes $U,V$ have no edges between them, making every vertex of $U$ a twin of a representative of $V$ changes the objective by $|U|(s(v)-s(u))$. Choose the direction with nonnegative change.

Among graphs maximizing the objective, choose one maximizing the sum of squared false-twin class sizes. The operation cannot split any old false-twin class and merges $U,V$, so it would strictly increase that secondary quantity. Therefore no two distinct classes can be nonadjacent. An objective maximizer is a complete multipartite graph. This edge-triangle symmetrization works for every real $c$, with no assumption on its sign.

For positive part sizes $a_1,\dots ,a_q$, the correct multipartite formula isThe first sum in the printed intermediate formula has inconsistent indices; the edge count is the pairwise-product sum above. Fix two part sizes with sum $A$ and let $B$ be the sum of all other sizes. All terms varying with the pair have the formChoose a maximizing partition with the fewest nonempty parts. If $1-cB\le 0$, merging those two parts cannot decrease $F$ and reduces the number of parts, a contradiction. Therefore this coefficient is positive for every pair. If two integer sizes differ by at least two, moving one vertex from the larger to the smaller increases their product and hence $F$, again a contradiction. All sizes differ by at most one, so a maximizer is a Turan graph. This is balancing a multipartite edge-triangle objective.

Next maximize the same polynomial on the compact simplex of nonnegative real sizes summing to $n$, starting with at least two possible parts. Choose a maximizer with the smallest positive support. The merging argument still applies, and now varying two positive unequal sizes towards equality improves the product. Thus every positive size is $n/q$ for some integer $q$. A two-part choice has value $n^2/4>0$ when $n>0$, so $q\ge 2$. The optimum is attained at rational sizes, and thereforeOne may take the initial simplex to have $\max (n,2)$ coordinates, so it includes every multipartite graph obtained above; zero coordinates are discarded.

Set $c=9/(4n)$. Dividing the right side by $n^2$ givesbecause $q$ is an integer at least two. Rearranging provesEquality in the continuous calculation occurs at two or three equal parts, explaining the triangle support line between bipartite and tripartite Turan graphs.

We prove edit-distance stability for clique-free graphs by induction on $r$, using the symmetric difference of edge sets as the distance. For $r=1$, a $K_2$-free graph is edgeless, and there is nothing to change. For $r\ge 2$, choose a vertex of maximum degree $d$, let $A$ be its neighbourhood and put $B=V(G)\setminus A$. Then $G[A]$ is $K_r$-free. WriteBoth deficits are nonnegative by the Turan theorem. Since every vertex of $B$ has degree at most $d=|A|$,The complete $r$-partite graph formed from an $(r-1)$-partite Turan graph on $A$ and the new class $B$ has at most $t_r(n)$ edges. Thus $L=t_r(n)-t_{r-1}(d)-|A||B|\ge 0$, and direct subtraction givesBy induction, edit $G[A]$ into a complete $(r-1)$-partite graph using at most $3D_A$ changes. Delete the $b$ edges inside $B$, and add the $m$ missing edges between $A$ and $B$. The resulting graph is complete $r$-partite on the same vertex set, andwhere the inequality uses $m\ge 2b$. The required edit distance is at most $3k$. Empty partition classes are allowed; a sufficiently dense nondegenerate case has the usual full complement of classes.

For the odd-cycle conclusion, use two standard consequences of the Szemerédi regularity lemma, stated explicitly. The triangle removal lemma says that for every $\alpha >0$, some $\beta >0$ ensures that a graph with at most $\beta n^3$ triangles in a graph can be made triangle-free by deleting at most $\alpha \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, for all sufficiently large $n$. Also, for each fixed odd length $\ell \ge 3$ and each $\beta >0$, there is $\zeta >0$ such that a graph with at least $\beta n^3$ triangles in a graph contains at least $\zeta n^{\ell }$ copies of $C_{\ell }$.

For clarity, the latter odd-cycle copies from positive triangle density consequence follows by applying regularity with error small relative to $\beta$, removing exceptional, irregular and very sparse pairs, and retaining a triangle in a graph among the remaining regular dense pairs. The graph embedding lemma for regular pairs counts a positive constant times $n^{\ell }$ embeddings of any fixed graph properly three-coloured into those three clusters, including $C_{\ell }$. Dividing by the fixed number of descriptions of a cycle gives the same conclusion for unlabelled copies.

Apply triangle in a graph removal with $\alpha =ϵ$, and take the resulting $\beta$. A $C_{2013}$-free graph cannot have $\beta n^3$ triangles in a graph for large $n$, by the preceding consequence. Delete at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges to obtain a triangle-free $G^{\prime }$. With $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$,Apply the proved stability result with $r=2$. The resulting complete bipartite graph $H$ satisfiesChoose $n_0(ϵ)$ also large enough that $3n/4\le 4ϵN$. Then the distance is at most $11ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$.

For the unheaded continuation, use the same $\beta$ and its associated $\zeta$, and set $\delta =\zeta /2$. Having at most $\delta n^{2013}$ cycles rules out $\beta n^3$ triangles in a graph just as before. The identical deletion and stability calculation applies. A sufficiently small $\delta =\delta (ϵ)>0$ gives the same $11ϵ$ bound.

In this enumeration problem, monotone means subgraph-closed graph property: both deleting vertices and deleting edges preserve membership. This is a decreasing convention, rather than the increasing-edge convention often used for random-graph thresholds. Assume first that the property is proper and has graphs of arbitrarily large orders. These are the usual nondegenerate hypotheses for the formula.

Put $r+1=\min \{\chi (F):F\notin \mathcal{Q}\}$. Every graph of chromatic number at most $r$ belongs to $\mathcal{Q}$. In particular, all subgraphs of a fixed balanced Turan graph $T_r(n)$ belong. Choosing each of its edges independently as present or absent givesFor the upper bound, fix $F\notin \mathcal{Q}$ with $\chi (F)=r+1$. Every member of $\mathcal{Q}$ is $F$-free, by closure under subgraphs.

We use the following standard regularity consequences. For every sufficiently small regularity error $\eta$, large minimum cluster count $q_0$, and fixed positive density cutoff $d$, the Szemerédi regularity lemma gives an equitable partition into $q_0\le q\le M$ clusters and an exceptional set of at most $\eta n$ vertices, with at most $\eta q^2$ irregular pairs. The graph embedding lemma for regular pairs says that a fixed graph with a prescribed proper colouring embeds into the corresponding clusters if all its required cross pairs are regular with density at least $d$, provided $\eta$ is sufficiently small relative to $d$ and the graph. Hence the reduced graph of a regularity partition, joining regular pairs of density at least $d$, is $K_{r+1}$-free: such a clique would embed $F$.

By the Turan theorem, this reduced graph has at most $(1-1/r)q^2/2$ edges. On its dense pairs allow arbitrary choices of original edges, giving at most $(1-1/r)n^2/2+O(n)$ free binary choices. All edges within clusters, touching the exceptional set, or lying in irregular pairs contribute $O((\eta +1/q_0)n^2)$ further choices. On each remaining pair there are at most $d$ times its number of possible edges. The elementary binary entropy estimatebounds the total sparse-pair contribution by $H_2(d)n^2/2$. The partition and pair classifications have at most $(M+1{)}^n{2}^{O(M^2)}$ descriptions, whose logarithm is $O(n)$ since $M$ is fixed. Choose $q_0$ large, then $d$ small, then $\eta$ sufficiently small; their total error can be made arbitrarily small. This provesIt is the enumeration of subgraph-closed graph properties.

For the hereditary extension, a hereditary graph property is closed under induced subgraphs. Define the clique-independent partition class $\mathcal{C}(a,b)$, for $0\le b\le a$, to consist of graphs partitionable into $a$ possibly empty classes, exactly $b$ designated as cliques and the other $a-b$ designated as independent sets; cross edges are unrestricted. Thus $a$ is the total number of classes. The colouring number of a hereditary graph property isUse value zero if this set is empty, and infinity for the class of all graphs.

$r(\mathcal{C}(a,b))=a$ for $a\ge 1$. The lower bound follows from the definition. For the upper bound, fix any $s\in \{0,\dots ,a+1\}$ and a balanced partition of a large $N$-vertex set into $a+1$ classes with $s$ clique classes. Independent choices of cross edges give $2^{(1-1/(a+1))N^2/2-O(1)}$ distinct graphs in $\mathcal{C}(a+1,s)$. On the other hand, all graphs in $\mathcal{C}(a,b)$ can be described by at most $a^N$ partitions, each with at most $(1-1/a)N^2/2$ unrestricted cross pairs. The former count is strictly larger for large $N$, so $\mathcal{C}(a+1,s)$ is not contained in $\mathcal{C}(a,b)$ for any $s$. A contained class with even more parts would contain one of these $(a+1)$-part classes by making unused parts empty, so it is also impossible.

The main changes for the hereditary graph enumeration theorem are as follows. The lower bound now uses a contained class $\mathcal{C}(r,b)$: within-class edges are fixed as complete or empty, and the balanced cross pairs still give $(1-1/r)n^2/2-O(1)$ free edge choices. For the upper bound, since no $\mathcal{C}(r+1,b)$ is wholly contained in $\mathcal{P}$, choose one forbidden induced graph $F_b\in \mathcal{C}(r+1,b)\setminus \mathcal{P}$ for each $b=0,\dots ,r+1$.

Use the standard induced regularity template lemma: for a fixed finite forbidden induced family and any error tolerance, a regularity refinement gives bounded-size templates with internal clique/independent types and cross pairs classified as sparse, almost complete, or intermediate. A clique of intermediate pairs on $a$ classes realizes every fixed induced pattern consistent with the internal types of those classes. This induced embedding conclusion uses a Ramsey refinement within clusters and regularity for both edges and nonedges; the total exceptional-pair cost can be made arbitrarily small. Applied to the $F_b$, a clique on $r+1$ intermediate classes would realize the forbidden $F_b$ whose number of clique types is $b$. Thus the graph of intermediate pairs is $K_{r+1}$-free. Only intermediate pairs contribute unrestricted binary choices; sparse pairs and the missing edges in almost-complete pairs each have the same entropy bound as before. The Turan theorem and the earlier counting argument now giveThis formula assumes $1\le r<\infty$. For the universal property the count is exactly $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$; a hereditary property of bounded order has $r=0$ and has no graphs on sufficiently large vertex sets, so the displayed expression with $1/r$ is not applicable.

For a proper subgraph-closed graph property, any contained $\mathcal{C}(a,b)$ must have $b=0$: if $b\ge 1$, it contains arbitrarily large complete graphs, and closure under subgraphs would force every graph into the property. Consequently its colouring number is exactly one less than the least chromatic number of an excluded graph. The excluded family of an intersection is the union of the two excluded families, whose minimum chromatic number is the smaller of their minima. Therefore $r(\mathcal{P}\cap \mathcal{Q})=\min (r(\mathcal{P}),r(\mathcal{Q}))$ for subgraph-closed properties, with the universal case treated by $r=\infty$.

For hereditary properties take $\mathcal{P}=\mathcal{C}(2,0)$ and $\mathcal{Q}=\mathcal{C}(2,2)$, both of colouring number two. A graph in their intersection is both bipartite and a union of two cliques. A clique in a bipartite graph has at most two vertices; hence every such graph has at most four vertices. The intersection contains no complete clique-independent class on arbitrarily large orders, so $r(\mathcal{P}\cap \mathcal{Q})=0<2$. This also demonstrates why the bounded-order exception to the enumeration formula is necessary.

Expose the independent coordinates one at a time and define the Doob exposure martingaleFor a fixed exposed prefix, couple the future coordinates identically under two choices of $Z_i$. The coordinate-change hypothesis bounds the difference of the resulting conditional expectations by $c_i$. Thus the increment $D_i=M_i-M_{i-1}$ has conditional mean zero and lies in a conditional interval of length at most $c_i$. This range bound, rather than merely $|D_i|\le c_i$, gives the sharp constant in the McDiarmid inequality.

Here is a proof of the needed Hoeffding lemma. For a mean-zero random variable $X$ in an interval of length $c$, let $h(u)=\log \mathbb{E}{e}^{uX}$. Its second derivative is the variance under the exponentially tilted distribution. A random variable in $[a,b]$ has variance at most $(b-a{)}^2/4$: the inequality $\mathbb{E}[(X-a)(b-X)]\ge 0$ gives $\mathrm{Var}X\le (\mathbb{E}X-a)(b-\mathbb{E}X)\le (b-a{)}^2/4$. Hence $h^{\prime \prime }(u)\le c^2/4$, and $h(0)=h^{\prime }(0)=0$ imply $h(u)\le u^2{c}^2/8$, for either sign of $u$.

Apply this conditionally to each increment and iterate the conditional expectation:For $u>0$, Markov's inequality bounds the upper tail by $\exp (-ut+u^2\sum c_i^2/8)$. Taking $u=4t/\sum c_i^2$ and then applying the same argument to $-f$ givesAt $t=0$ the bound is immediate. If all $c_i$ vanish, $f$ is constant on the product support and the positive tails are zero, so that degenerate case is handled directly.

For a binomial random graph, let coordinate $i$ be the entire vector of edges from vertex $i$ to vertices of smaller label. The coordinates are independent finite probability spaces. Changing coordinate $i$ changes only edges incident to that one vertex. Deleting the vertex gives the same graph under both outcomes, and each outcome's chromatic number is either that graph's chromatic number or one more. Thus the coordinate range is at most one. Taking all $c_i=1$ and $t=\lambda \sqrt{n}$ proves vertex exposure for chromatic number:Using individual edges as coordinates would give a weaker scale; grouping the incident edges is what yields the required bound.

For the expectation asymptotic, take fixed $0<p<1$, put $b=1/(1-p)$, and write $L={\log }_{b}n$. We outline both bounds and the step that turns probability estimates into an expectation estimate. For each fixed $\gamma >0$, the expected number of independent sets of size $k=\lceil (2+\gamma )L\rceil$ isIts logarithm is $k\log n-\frac{1}{2}k(k-1)\log b-O(k\log k)=-{\Omega }_{\gamma }((\log n{)}^2)$. Thus Markov's inequality gives $\alpha (G)\le (2+\gamma )L$ with probability tending to one, and $\chi (G)\ge n/\alpha (G)$ yields the corresponding lower bound on its expectation.

For the upper bound, set $m_0=\lceil n/(\log n{)}^2\rceil$ and $k=\lfloor (2-\gamma )L\rfloor$, with $0<\gamma <1$. The key uniform fact is that every vertex subset of size at least $m_0$ contains an independent $k$-set with probability tending to one. For a fixed subset of size $m$, let $X$ count its independent $k$-sets and let $\mu =\left(\genfrac{}{}{0ex}{}{m}{k}\right)b^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. The normalized dependency sum in Janson inequality is bounded byThe $j=2$ term is $O(k^4/m^2)$. The remaining overlap terms give the same order or less: use $\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(\genfrac{}{}{0ex}{}{m-k}{k-j}\right)/\left(\genfrac{}{}{0ex}{}{m}{k}\right)\le (2k^2/m{)}^j$ for large $n$, and split the sum at $k/2$. For the lower half the terms beyond $j=2$ decrease at the initial endpoint and are exponentially small at the other endpoint; for the upper half, $k\le (2-\gamma /2){\log }_{b}m$ makes every endpoint exponent negative of order $(\log n{)}^2$. Also $1/\mu$ is exponentially small on that scale. The exponential form of Janson inequality therefore gives, uniformly for $m\ge m_0$,for a positive constant depending only on $p,\gamma$. A union bound over at most $2^n$ subsets succeeds, because $m_0^2/k^4$ is of order $n^2/(\log n{)}^8\gg n$. This is independent sets in every large subset of a dense random graph.

On that event, repeatedly remove an independent $k$-set and assign it one new colour until fewer than $m_0$ vertices remain; colour the remainder individually. This gives $\chi (G)\le n/k+m_0$. The failure probability is exponentially small compared with $1/\log n$, and always $\chi (G)\le n$, so the failure event contributes negligibly to the expectation. Combining the upper and lower bounds and then letting $\gamma \downarrow 0$ provesThis is the chromatic number of a binomial random graph asymptotic. The slash in the printed expression must be read with $2{\log }_{1/(1-p)}n$ as the denominator; a multiplicative reading would eventually exceed $n$. At the endpoint probabilities $p=0$ and $p=1$, the chromatic numbers are respectively one and $n$ for $n\ge 1$, so this logarithmic formula is intended for $0<p<1$.