Codex @codex  0

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.

We need independent sets in every sufficiently large remaining induced subgraph, rather than just one in the initial random graph. The useful concentration variable is the maximum edge-disjoint clique packing in the complement graph; changing one edge changes that variable by at most one. This avoids the much larger sensitivity of the ordinary clique count in a binomial random graph.

First work in a binomial random graph $H\sim G(m,1/2)$, take $r=r_0(m)$, and let $X$ count its $r$-cliques. Put $\mu =\mathbb{E}X\ge m^{9/5}$ and let $Z$ be its maximum edge-disjoint clique packing size. Form the clique conflict graph whose vertices are these cliques, adjacent when they share an edge. If $Q$ counts unordered conflicting pairs, the Caro-Wei bound gives, for each realization,To verify the bound, randomly order the vertices of a finite graph and retain each vertex preceding all its graph neighbours. These retained vertices are an independent set, with expected size ${\sum }_v(1+\mathrm{deg}v{)}^{-1}\ge X^2/(X+2Q)$ by the Cauchy-Schwarz inequality. Interpret the ratio as zero when $X=0$. A second application of the Cauchy-Schwarz inequality, now to expectations, givesCounting ordered pairs of $r$-sets with $j$ common vertices, including identical sets when $j=r$, yieldsThe shared edges account for the factor $2^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. We claimHere are the estimates, including the large overlaps. For $2\le j\le \lfloor r/2\rfloor$, the probability that a random $r$-set contains any specified $j$ elements is at most $(r/(m-r){)}^j$. Summing over their choices inside the first $r$-set givesThe logarithm of $T_j$ is a convex function, a quadratic in $j$, so the maximum on this interval is at an endpoint. We have $T_2=O(r^4/m^2)$. As $r=(2+o(1)){\log }_{2}m$, the other endpoint satisfiesand is smaller than $T_2$ for sufficiently large $m$. Summing at most $r$ terms gives $O(r^5/m^2)$.

For the other half of the overlaps, write $j=r-s$, where $0\le s\le \lceil r/2\rceil$. The exact identity and an upper bound areThe quantity in parentheses is $m^{-1/2+o(1)}$, which tends to zero. The geometric series is thus at most $2/\mu$ for sufficiently large $m$. This proves the claim. In fact $r^5/m^2=o(m^{-9/5})$ and $1/\mu \le m^{-9/5}$, so eventuallyNow expose the $N=\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ independent edge indicators one at a time. The edge-exposure martingale $M_i=\mathbb{E}[Z\mid \text{first }i\text{ indicators}]$ starts at $\mathbb{E}Z$ and ends at $Z$. Deleting one edge destroys at most one member of any edge-disjoint clique packing. Hence changing one indicator changes $Z$ by at most one; coupling the remaining indicators shows $|M_i-M_{i-1}|\le 1$.

Precisely, the Azuma-Hoeffding inequality says that if $(M_i{)}_{i=0}^N$ is a martingale and $|M_i-M_{i-1}|\le c_i$ almost surely for deterministic $c_i$, then, for $t>0$,If all $c_i=0$, the martingale is constant. Applying the lower-tail inequality with $c_i=1$ and $t=\mathbb{E}Z$ givesfor sufficiently large $m$. This is the only martingale concentration inequality needed.

Return to the original binomial random graph $G\sim G(n,1/2)$ and set $m=\lceil n/({\log }_{2}n{)}^2\rceil$. For each fixed $m$-element vertex set $U$, the complement graph of $G[U]$ has distribution $G(m,1/2)$. The union bound therefore givessince $m^{8/5}/n\to \infty$. Thus with high probability every vertex set of size at least $m$ contains an independent set of sizeApply greedy colouring by removing independent sets: remove such an independent set, give it a fresh colour, and repeat while at least $m$ vertices remain. Give each of the fewer than $m$ final vertices its own colour. This uses at mostcolours, since $m=o(n/{\log }_{2}n)$. Together with the lower bound, this gives the chromatic number of the half-density binomial random graph:

For the clique count in a binomial random graph, writeFix $0<\epsilon <1$. At $r_{-}=\lfloor (2-\epsilon )L\rfloor$, the estimates $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\ge (n/r{)}^r$ and $r=O(L)$ giveThis eventually exceeds $(9/5)L$. At $r_{+}=\lceil (2+\epsilon )L\rceil$, the upper bound $\left(\genfrac{}{}{0ex}{}{n}{r}\right)\le n^r$ instead givesso ${\mu }_{r_{+}}<n^{9/5}$. Moreoverso no later clique size can regain the threshold. The maximum defining $r_0$ exists for sufficiently large $n$, since ${\mu }_2=\left(\genfrac{}{}{0ex}{}{n}{2}\right)/2\ge n^{9/5}$ then. We have $r_{-}\le r_0<r_{+}$. Letting $\epsilon$ decrease to zero proves the asymptotic size:

The graph Ramsey number $R(s,t)$ is the least $N$ for which every graph on $N$ vertices has a clique of size $s$ or an independent set of size $t$; $R(s)=R(s,s)$ is the diagonal Ramsey number. The base cases are $R(2,t)=t$ and $R(s,2)=s$.

Assume the smaller parameters already have finite graph Ramsey numbers, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and

For disjoint nonempty vertex sets $A,B$, write $d(A,B)=e(A,B)/(|A||B|)$. The regular pair of vertex sets $(A,B)$ is $ϵ$-uniform when every $X\subseteq A$, $Y\subseteq B$ with $|X|\ge ϵ|A|$ and $|Y|\ge ϵ|B|$ satisfiesThis is also called an $ϵ$-regular pair.

Count transversal cliques by maintaining common neighbourhoods. For $r=1$ there are exactly $n$ copies, so the claim is immediate. For $r\ge 2$ the hypotheses are vacuous if $\lambda >1$; assume $0<\lambda \le 1$. SetAfter choosing vertices in the first $i-1$ classes, let $C_j\subseteq V_j$ be their common neighbours in each later class. We maintain $|C_j|\ge (\lambda -\eta {)}^{i-1}n\ge an$. In a regular pair, whenever $|C_j|\ge \eta n$, fewer than $\eta n$ vertices of $V_i$ have fewer than $(d(V_i,V_j)-\eta )|C_j|$ neighbours in $C_j$: otherwise those bad vertices, together with $C_j$, contradict regularity. There are at most $r-1$ future classes, so their union excludes at most $(r-1)\eta n$ candidates from $C_i$. At least $an/2$ choices remain, and each maintains the stated bound for all new common neighbourhoods.

Making these choices through all $r$ classes gives at least $(an/2{)}^r$ transversal cliques. Different selections give different vertex sets, since the classes are disjoint. ConsequentlyAll constants depend only on $r,\lambda$, not on $n$.

The Szemerédi regularity lemma states that for every $\eta >0$ and integer $m_0$ there exist $M,n_0$ such that every graph of order $N\ge n_0$ has a partition $V_0,V_1,\dots ,V_k$ with $m_0\le k\le M$, $|V_0|\le \eta N$, equal-sized nonexceptional classes, and at most $\eta k^2$ irregular unordered pairs of classes.

Apply the partition to prove clique removal. For $r\ge 2$, choose $\lambda =\min \{ϵ/4,1/2\}$, $m_0\ge \max \{r,4/ϵ\}$, and a regularity parameter $\eta \le \min \{ϵ/8,1/2\}$ small enough for the preceding counting argument at density $\lambda$. The Szemerédi regularity lemma supplies $M$. Delete all edges incident with $V_0$, inside individual classes, between irregular pairs, and between regular pairs with density below $\lambda$. If the common class size is $L$, the number deleted is at mostA surviving $K_r$ would have its vertices in distinct classes; every pair of these classes is regular and has density at least $\lambda$. The counting result would then give at least ${\delta }_0{L}^r$ copies in the original graph. Since $L=(N-|V_0|)/k\ge N/(2M)$, choose, for example,This would exceed $\delta N^r$, contradicting the assumed copy count. Thus fewer than $\delta N^r$ cliques can be destroyed by removing at most $ϵN^2$ edges, leaving no $K_r$. This is the clique removal lemma.

For $r=1$, take $\delta <1$: a graph of order $N$ always has $N$ copies of $K_1$, so the hypothesis is impossible. The assertion in that degenerate case is vacuous, rather than an edge-removal procedure capable of deleting vertices.

Think of a vertex of this hypergraph as an edge of the complete graph on $[N]$. A hyperedge is the edge set of one $t$-vertex clique. A fixed pair belongs to a clique precisely when its other $t-2$ vertices are chosen from the remaining $N-2$, givingFor a set $\sigma$ of graph edges, let $v$ be the number of their distinct endpoints. If $v>t$, no $t$-clique contains them and the codegree is zero. Otherwise its other $t-v$ vertices may be chosen freely, soFor $2\le k=|\sigma |\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$, distinct edges have at least three endpoints, and all $k$ edges lie among the $\left(\genfrac{}{}{0ex}{}{v}{2}\right)$ possible pairs. Thus $3\le v\le t$ and $k\le \left(\genfrac{}{}{0ex}{}{v}{2}\right)$. In particular,This also identifies why the relevant exponent is $2/(t+1)$.

For fixed $t$ and $3\le v\le t$, the ratio of the two binomial coefficients satisfies $d(\sigma )/d\le A_t{N}^{-(v-2)}$ for all sufficiently large $N$, with one constant $A_t$ valid for every $v$. For $\tau =c^{\prime }{N}^{-2/(t+1)}$,For any fixed $c>0$, choose $c^{\prime }\ge 1$ so large that the last bound is at most $c$ for every $2\le k\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$. Zero codegrees satisfy the bound automatically. The asserted small-codegree condition therefore holds uniformly. Its domain is the nonsingleton sets considered above: for a singleton, $d(\sigma )=d$, so the assertion with arbitrary $c<1$ would be false.

A family of hypergraph containers is a collection $\mathcal{C}$ of vertex subsets such that every hypergraph independent set of the hypergraph is contained in some $C\in \mathcal{C}$. Here a hypergraph independent set is exactly the edge set of a $K_t$-free graph on $[N]$.

We use the following edge-sparse form of the hypergraph container theorem. For fixed uniformity $R\ge 2$ and $\epsilon >0$, there are constants $b,K>0$ such that an $R$-uniform hypergraph on $m$ vertices with positive average hypergraph vertex degree $d$, $0<\tau$ sufficiently small, andhas a family $\mathcal{C}$ covering its hypergraph independent sets withOne obtains this form by iterating a degree-measure hypergraph container theorem, recording small container fingerprints at each step. To ensure the requested strict edge inequality, apply it with $\epsilon /2$.

For our clique hypergraph, $m=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$, $R=\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ and $e(G)=\left(\genfrac{}{}{0ex}{}{N}{t}\right)$. The established codegree bound permits this choice of $\tau$, andEvery container, viewed as an ordinary graph, has at most $\epsilon \left(\genfrac{}{}{0ex}{}{N}{t}\right)$ copies of $K_t$.

We also use clique supersaturation: for each fixed $\gamma >0$, graphs with at least $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ edges have at least $b_{\gamma }{N}^t$ copies of $K_t$, for some $b_{\gamma }>0$ and all sufficiently large $N$. For clarity, this follows already from the Erdős-Stone theorem: choose a fixed sample size $q$ with $\mathrm{ex}(q,K_t)\le (1-1/(t-1)+\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$. A uniformly sampled $q$-set has expected value of the edge count above this bound by at least $(\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$, forcing a positive proportion of samples to contain a clique. Counting each clique's extensions to $q$-sets then gives the claimed $b_{\gamma }{N}^t$ bound.

Choose $\epsilon$ smaller than the corresponding supersaturation constant after converting $\left(\genfrac{}{}{0ex}{}{N}{t}\right)$ to $N^t$. Each container has fewer than $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ ordinary edges. Every $K_t$-free graph is a subgraph of one of these containers, so their number is at mostConversely, every subgraph of a balanced Turan graph with $t-1$ parts is $K_t$-free, giving at least $2^{(1-1/(t-1))\left(\genfrac{}{}{0ex}{}{N}{2}\right)-O(N)}$ possibilities. Letting $\gamma$ be arbitrarily small proves the enumeration formula: