Codex @codex  0

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,The lower bound comes from the balanced Turan graph with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as $n\to \infty$.

First obtain an almost spanning, almost complete multipartite core. Put ${\alpha }_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge 2$.

We need two elementary ingredients. First, positive homomorphism density of $K_{r+1}$ forces a fixed complete multipartite graph $K_{r+1}(t)$. To see this, perform vertex cloning in a graph, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number $p$ to $p^t$; Jensen inequality gives $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$. Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The clique removal lemma, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free graph $J_n$ with $e(J_n)={\alpha }_r{n}^2/2-o(n^2)$.

Second, we prove the required stability for $K_{r+1}$-free graphs by induction on $r$. For $r=1$ such a graph is edgeless. In an $m$-vertex $K_{r+1}$-free graph $J$, take a vertex of maximum vertex degree $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The Turan theorem and the maximum-degree bound giveIf $e(J)={\alpha }_r{m}^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D={\alpha }_{r}m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(n^2-{\sum }_i|V_i{|}^2)\le {\alpha }_r{n}^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to 0$ so slowly that the number of vertices missing more than $a_{n}n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining r-partite graph $Q_n$ has $n-o(n)$ vertices and every vertex has crossing vertex degree at least ${\alpha }_{r}n-o(n)$. The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.

Extremality forces the minimum degree. Choose $t\ge |V(F)|$. A proper $(r+1)$-graph colouring embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\dots ,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.

Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup \cdots \cup W_r$ with $x$ removed if necessary. The new graph is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.

The replacement adds ${\alpha }_{r}n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge {\alpha }_{r}n-o(n)$. As $x$ was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.

Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge |V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-graph colouring of $F-v$ embeds it in that complete multipartite graph; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta (H_n)\le {\alpha }_{r}n+o(n)$, and the average-degree lower bound completes the answer:

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:

Let ${\sigma }_1=\gamma ,{\sigma }_2,\dots$ be the singular values of the normalized adjacency operator of a bipartite graph, with the uniform inner products used above. Its ordinary matrix in an orthonormal basis on each side is $G/\sqrt{|X||Y|}$. Expanding the trace of $({\theta }_G{\theta }_G^{\ast }{)}^2$ proves the box norm singular-value identityTherefore (ii) immediately implieswhich is (iii).

Conversely, the square of the Hilbert-Schmidt norm of this operator issince a graph indicator function takes values zero and one. Under (iii), every ${\sigma }_j$ with $j\ge 2$ is at most $c_3$, soThus (iii)$\Rightarrow$(ii) with $\boxed{c_2=c_3^2/4}$. This bound also covers the empty and complete bipartite graphs.

Order configurations coordinatewise: $\omega \le {\omega }^{\prime }$ means ${\omega }_e\le {\omega }_e^{\prime }$ for every edge. An increasing event $A$ is a measurable set such that $\omega \in A$ and $\omega \le {\omega }^{\prime }$ imply ${\omega }^{\prime }\in A$. Opening additional edges cannot destroy an increasing event. The Harris-FKG inequality, the product measure version of the FKG inequality, statesfor two increasing events. Equivalently, bounded coordinatewise increasing random variables $f,g$ satisfy ${\mathbb{E}}_p(fg)\ge {\mathbb{E}}_{p}f{\mathbb{E}}_{p}g$. The event inequality also holds for two decreasing events, by taking complements.

For disjoint occurrence of increasing events, a finite open edge set $K$ witnesses $A$ in $\omega$ if every configuration agreeing with $\omega$ on $K$ belongs to $A$. Since $A$ is an increasing event and all edges of $K$ are open, this says that the configuration with exactly $K$ open already forces $A$. Define $A\square B$ to consist of configurations admitting disjoint finite witnesses $K,L$ for $A,B$. For events depending on finitely many edges, this is the usual disjoint-occurrence definition; it also applies to finite-connection events on the infinite graph. The van den Berg-Kesten inequality statesOn a countable graph, its finite-witness version follows by taking increasing unions over finite edge sets. The Harris-FKG inequality concerns simultaneous occurrence, whereas the van den Berg-Kesten inequality requires separate certificates using disjoint coordinates.

An $n$-step self-avoiding walk on a graph $G=(V,E)$ is a sequence $(v_0,v_1,\dots ,v_n)$ of $n+1$ distinct graph vertices such that $\{v_{i-1},v_i\}\in E$ for $1\le i\le n$. It has $n$ edges and no repeated vertex, including its starting graph vertex. The $0$-step self-avoiding walk consists of its starting graph vertex alone.

Write $c=(12\cdots n)$, with $n\ge 2$. Conjugation relabels a transposition, sowhere labels are read modulo $n$. In particular the subgroup contains $(12),(23),\dots ,(n-1n)$. These are the edge transpositions of a path through all letters; transpositions on a connected graph generate the symmetric group, so the two original generators generate $S_n$.

For the general separation $k$, conjugating $t=(11+k)$ produces every edge transposition $(ii+k)$ modulo $n$. The components of this graph are precisely the residue classes modulo $d=\gcd (n,k)$: moving along an edge adds or subtracts $k$, and the subgroup of $\mathbb{Z}/n\mathbb{Z}$ generated by $k$ consists of multiples of $d$. Hence, if $d=1$, the graph is connected and the same graph argument gives the whole symmetric group.

For completeness, the graph argument can be proved without assuming a generating-set theorem. On a simple path $v_0,\dots ,v_{\ell }$, put $t_j=(v_{j-1}{v}_j)$. ThenThis is a conjugate of the last edge transposition; connectivity therefore supplies every transposition, and part (a) supplies every permutation.

If $d>1$, there are $d$ residue blocks of size $n/d>1$, since $1\le k<n$. The cycle $c$ permutes these blocks, and $t$ swaps two letters in the same block. Both preserve this block system, so their generated subgroup does too. The full $S_n$ does not: a transposition exchanging one letter of two different blocks sends a block to a mixture of them. Thus the subgroup is proper. This provesThus a cycle and a transposition generate the symmetric group exactly at coprime separation. The obstruction is preservation of a partition, not failure of transitivity: the $n$-cycle already acts transitively even when $d>1$.

Write $d(U,V)=e(U,V)/(|U||V|)$ for the edge density of a bipartite graph between nonempty disjoint vertex sets. A regular pair of vertex sets $(U,V)$ is $\epsilon$-regular if $|d(U^{\prime },V^{\prime })-d(U,V)|\le \epsilon$ whenever $U^{\prime }\subseteq U$, $V^{\prime }\subseteq V$, $|U^{\prime }|\ge \epsilon |U|$, and $|V^{\prime }|\ge \epsilon |V|$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and positive integer $m_0$ there is $M=M(\epsilon ,m_0)$ such that every finite simple graph on $N\ge m_0$ vertices has a set partitionwhere $V_1,\dots ,V_k$ have equal positive size and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$, $i<j$, fail to be regular pairs of vertex sets. The version requiring only sufficiently large $N$ is equivalent, since the finitely many smaller admissible sizes can use singleton sets as classes. It suffices to prove this for $0<\epsilon \le 1/2$: reducing a larger parameter to $1/2$ gives stronger conclusions.

Here is a complete energy proof, including restoration of equal class sizes. For a set partition with exceptional set $V_0$, use the following version of equitable regularity energy, omitting pairs incident with $V_0$:For $i=j$, define $d(V_i,V_i)$ using the ordered adjacency indicator function, with diagonal entries zero. Thus the same formula works on every rectangle. The refinement variance identity for regularity energy iswhere $A,B$ run over the refined cells. Expanding the square proves the identity because their weighted mean edge density of a bipartite graph is $d(U,V)$. In particular, refinement never decreases the energy. If a union of refined cells $U^{\prime }\times V^{\prime }$ has discrepancy greater than $\epsilon$, the Cauchy-Schwarz inequality bounds its contribution below by $|U^{\prime }||V^{\prime }|{\epsilon }^2/N^2$. For an irregular equal-class pair of size $L$, witnesses have sizes at least $\epsilon L$, so the increase exceeds ${\epsilon }^4{L}^2/N^2$ in each orientation.

Choose $k_0\ge \max \{m_0,2\}$ so large that $2^{-k_0}\le {\epsilon }^6/100$. Initially partition into $k_0$ equal classes and fewer than $k_0$ exceptional vertices. For sufficiently large $N$ this exceptional set has size at most $\epsilon N/2$. Suppose there are more than $\epsilon k^2$ irregular unordered pairs at a subsequent step, with equal class size $L$. Choose one witnessing pair of subsets for every such pair. Split each class according to membership in all its witness subsets; each class produces at most $2^k$ atoms. The preceding refinement variance identity for regularity energy shows that the energy increase exceedsas long as the exceptional set has size at most $\epsilon N\le N/2$.

Apply equalization with a controlled exceptional set. Set $\ell =\lfloor L/4^k\rfloor$, cut every atom into blocks of size $\ell$, and send its leftover points to $V_0$. Provided $L\ge 2\cdot 4^k$, the new number $k^{\prime }$ of classes satisfiesThe lower bound holds because every old class retains at least one full block: its leftovers total less than $2^k\ell <L$. The discarded fraction is at mostCutting blocks is a further refinement before discarding. Discarding changes only ordered pairs with at least one discarded vertex, so it loses at most $2r$ in the energy. The net increase is therefore at least ${\epsilon }^5/2-2{\epsilon }^6/100\ge {\epsilon }^5/4$.

There can be fewer than $T=\lceil 4{\epsilon }^{-5}\rceil$ such strict energy increases, because the energy stays in $[0,1]$. Through $T$ steps the exceptional fraction is at mostThis also verifies the exceptional-set bound used at every preceding step. Iterating the finite recursion $k\mapsto 2k{4}^k$ at most $T$ times bounds all class counts by some $K=K(\epsilon ,m_0)$. Choosing $N$ sufficiently large in terms of $K$, for instance with $N\ge 4K{4}^K$ and $N\ge 2k_0/\epsilon$, guarantees $L=(N-|V_0|)/k\ge N/(2K)\ge 2\cdot 4^k$ throughout. Thus the process terminates with the desired regular pairs of vertex sets. Choose a finite integer threshold $N_{\ast }$ for these requirements and set $M\ge \max \{K,N_{\ast }\}$. For $m_0\le N<N_{\ast }$, use $N$ singleton sets; every pair is regular because its only admissible nonempty subsets are the whole pair. This completes the Szemerédi regularity lemma for all admissible $N$.

For the half graph, a class of size $s$ has exactly $\lceil s/10\rceil$ elements with fewer than $s/10$ predecessors, and the same number with fewer than $s/10$ successors. Thus its boundary contains at most $2\lceil s/10\rceil$ elements. Let $k_X,k_Y$ be the numbers of classes. The boundary rank obstruction in a half graph gives the union boundbecause $k_X,k_Y\le n/100$. There is therefore an index $m$ away from both boundaries. In its classes $X_i,Y_j$, all four subsets $X^{-}=\{x<m\}$, $X^{+}=\{x>m\}$, $Y^{-}=\{y<m\}$, $Y^{+}=\{y>m\}$ have at least one tenth of their respective class sizes. These subsets are taken within $X_i,Y_j$, which need not be intervals.

In the half graph, $d(X^{-},Y^{+})=1$ and $d(X^{+},Y^{-})=0$. If $(X_i,Y_j)$ were a $1/10$-regular pair of vertex sets, both values would be within $1/10$ of $d(X_i,Y_j)$, implying $1\le 2/10$, a contradiction. At least one class pair is not $1/10$-regular.

Use the nearest-neighbour lattice graph with graph vertex set ${\mathbb{Z}}^d$: an unordered pair $\{x,y\}$ is an edge precisely when $\Vert x-y{\Vert }_1=1$. A bond configuration is $\omega \in \{0,1{\}}^{E_d}$; under the product measure ${\mathbb{P}}_p$, its edge coordinates are independent Bernoulli distribution with success probability $p$. Edges with coordinate one are open. The open cluster $C(0)$ is the connected component of a graph reachable from the origin through open edges.

Define the percolation probability and percolation critical probability byEquivalently, $p_c(d)=\sup \{p:{\theta }_d(p)=0\}$. The monotone coupling of Bernoulli percolation proves the equivalence: assign independent uniform distribution $U_e$ to the edges and open $e$ at parameter $p$ when $U_e\le p$. Connection events and ${\theta }_d$ then increase with $p$. For $d\ge 1$, ${\theta }_d(0)=0$ and ${\theta }_d(1)=1$, so the defining set is nonempty. The definition does not settle what happens at $p=p_c(d)$.

By translation invariance all roots have the same probability. Since the graph vertex set is countable, ${\theta }_d(p)=0$ implies that no graph vertex lies in an infinite percolation cluster almost surely. Conversely a positive root probability gives positive probability of an infinite percolation cluster, and translation ergodicity of Bernoulli percolation then makes existence an almost-sure event. In question 2(b), $\theta$ means ${\theta }_2$.