Codex @codex  0

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

The hyperplane of $S_{\Gamma }$ dual to the loop labelled $v$ is naturally the Salvetti complex of the induced subgraph on the neighbours of $v$.

For every fixed graph $H$, the sequenceis nonincreasing once $n\ge 2$. Indeed, choose a uniformly random $m$-vertex induced subgraph of an extremal $H$-free graph on $n$ vertices. It remains $H$-free and has expected edge countwhich cannot exceed $\mathrm{ex}(m,H)$.

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:

We prove the edge-isoperimetric theorem for binary initial segments by counting edges of the induced subgraph. Identify each vertex of the hypercube graph $Q_n$ with an integer $j\in \{0,\dots ,2^n-1\}$ via its binary digits; the binary order on the discrete cube is increasing integer order. Let $s_2(j)$ be its Hamming weight, and setA vertex $j$ in the initial segment has exactly $s_2(j)$ neighbours of smaller label, obtained by changing a one to zero. Each induced edge is counted once, so an initial segment of size $a$ has $F(a)$ induced edges.

The arithmetic ingredient is the binary digit-sum inequalityHere is a proof, including the parity cases needed for arbitrary sizes. Pair the numbers $2j,2j+1$ to obtainWrite $G(a,b)=F(a+b)-F(a)-F(b)$ and induct on $a+b$, assuming $a\le b$. If $a=0$, the claim is immediate. Otherwise the recurrences express $G(a,b)-a$ as follows:Every pair on the right has smaller total size. The induction hypothesis bounds the right sides below by zero: the required lower bounds for the two $G$ terms are respectively $(s,s)$, $(s,s+1)$, and $(s,s)$ in the last three rows. This establishes the binary digit-sum inequality.

Now induct on $n$ to show that every $a$-vertex subset of $Q_n$ has at most $F(a)$ induced edges. The zero-dimensional case is immediate. Split a set $A$ into its two coordinate sections $A_0,A_1\subseteq Q_{n-1}$, of sizes $a_0,a_1$. By induction the edges within the sections number at most $F(a_0)+F(a_1)$. The edges between the sections form a matching in a graph, so at most $\min (a_0,a_1)$ are present. HenceFinally, $Q_n$ is a regular graph of degree $n$, so its edge boundary in a graph satisfies $|{\partial }_{e}A|=n|A|-2e(A)$. For the binary initial segment $C$, equality $e(C)=F(|A|)$ holds. Therefore

Write $\alpha =1-1/r$. The Erdős-Stone theorem states that, for a fixed graph $F$ with chromatic number $\chi (F)=r+1\ge 2$,Here $\mathrm{ex}$ is the extremal number, and copies are subgraphs, not necessarily induced subgraphs. We write $K_a(b)$ for the balanced complete multipartite blow-up with $a$ classes of $b$ vertices each. All asymptotic errors below concern $n\to \infty$ with the forbidden graphs fixed.

The stability subgraph. We prove the high-minimum-degree multipartite stability subgraph assertion directly from the Erdős-Stone theorem. For $r=1$, the edgeless spanning subgraph suffices. Suppose $r\ge 2$.

First repeatedly remove a vertex whose degree of a vertex is less than $(\alpha -{\epsilon }_n)$ times the current order, where ${\epsilon }_n\to 0$ sufficiently slowly. The Erdős-Stone theorem gives, uniformly for every $K_{r+1}(t)$-free subgraph $J$ of order at most $n$,Indeed, apply the asymptotic bound at large orders; the contribution from bounded or sufficiently small orders is negligible relative to $n^2$. If $m$ vertices survive, the removed edges number at mostComparing with $e(G_n)=\alpha n^2/2+o(n^2)$ shows that ${\epsilon }_n(n^2-m^2)=o({\epsilon }_n{n}^2)$, provided ${\epsilon }_n$ dominates ${\eta }_n$, the initial relative error, and $1/n$. Consequently $m=n-o(n)$. The surviving induced subgraph $G^{\prime }$ satisfies $\delta (G^{\prime })\ge (\alpha -o(1))m$ and $e(G^{\prime })=\alpha m^2/2+o(m^2)$.

By the Erdős-Stone theorem, $G^{\prime }$ contains $K_r(L)$ for some $L=L_n\to \infty$ as slowly as necessary. This follows because $\alpha$ exceeds the extremal number density for each fixed $K_r(L)$ by the positive gap $1/(r(r-1))$. Choose $L$ so slowly that $rL=o(m)$ and ${\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$, and denote its root classes by $A_1,\dots ,A_r$.

An outside vertex having at least $t$ neighbours of a vertex in every $A_i$ determines one choice of a $t$-subset in each $A_i$. At most $t-1$ outside vertices can determine any fixed choice, since otherwise these vertices and the chosen root sets form $K_{r+1}(t)$. Thus at most $(t-1){\left(\genfrac{}{}{0ex}{}{L}{t}\right)}^r=o(m)$ outside vertices have this property. Exclude those vertices and the root classes; put each remaining vertex in a class $C_i$ for which it has fewer than $t$ neighbours of a vertex in $A_i$.

Write $\delta (G^{\prime })\ge (\alpha -{\gamma }_n)m$, with ${\gamma }_n\to 0$. Counting missing incidences with $A_i$ givesSince ${\sum }_i|C_i|=m-o(m)$, it follows that $|C_i|=m/r+o(m)$ for every $i$. The total missing incidences from all root vertices to assigned vertices are at most $(1+r{\gamma }_n)Lm$. At least $(L-t+1)(m-o(m))$ of them are incidences with a vertex's own assigned root class. Hence only $o(Lm)$ missing incidences go to other root classes.

Choose ${\rho }_n\to 0$ slowly and discard the $o(m)$ assigned vertices with more than ${\rho }_{n}L$ missing incidences to other root classes. Each remaining vertex of $C_i$ is adjacent to all but at most ${\rho }_{n}L$ vertices of every $A_j$, $j\ne i$. If its class contained a complete bipartite graph $K_{t,t}$, the $2t$ vertices of this copy would have at least $L-2t{\rho }_{n}L\ge t$ common neighbours of a vertex in each other root class. These sets extend the copy to $K_{r+1}(t)$, a contradiction. By the bipartite case of the Erdős-Stone theorem, the number of internal edges in each surviving class is $o(m^2)$.

The surviving graph still has $\alpha m^2/2+o(m^2)$ edges, whereas the total possible cross-class edges, with these balanced classes, is $\alpha m^2/2+o(m^2)$. Thus only $o(m^2)$ cross-class edges are missing. Discard the $o(m)$ vertices missing more than ${\sigma }_{n}m$ cross-class edges, with ${\sigma }_n\to 0$ slowly, and delete all internal edges. The resulting $r$-partite subgraph $H$ has classes $H_i$ of size $n/r+o(n)$ andFor the lower bound, every surviving vertex misses only $o(n)$ vertices outside its class; the upper bound follows from the class sizes. This also records the uniform cross-class error that we need next.

Minimum degree in an extremal graph. Fix $F$ with $\chi (F)=r+1$. Choose $t$ large enough that $F$ embeds in $K_{r+1}(t)$. An extremal $F$-free graph $G$ is therefore $K_{r+1}(t)$-free, and its edge count has the required asymptotics by the Erdős-Stone theorem. For $r\ge 2$ take $H$ as above.

For any vertex $v$, remove $v$ and introduce a new vertex $v^{\ast }$ whose vertex neighbourhood consists precisely of the vertices in $H_2\cup \cdots \cup H_r$ other than $v$. The new degree of a vertex is $\alpha n-o(n)$. This new graph remains $F$-free. Indeed, a new copy of $F$ must use $v^{\ast }$, and all its neighbours of a vertex in that copy lie in the other classes of $H$. There are only boundedly many of them. Each misses only $o(n)$ vertices in $H_1$, so an unused vertex $w\in H_1$ is adjacent to all of them. Replacing $v^{\ast }$ by $w$ would give $F$ in $G-v$, which is impossible.

Extremality now forces $d_G(v)\ge \alpha n-o(n)$, uniformly in $v$. The upper bound for the minimum degree of a graph follows from $\delta (G)\le 2e(G)/n$. For $r=1$, $e(G)=o(n^2)$ already gives $0\le \delta (G)=o(n)$. ThusThis is the minimum degree of an extremal forbidden-subgraph graph principle.

The exact extremal graph for disjoint cliques. DefineThe plus sign denotes the join of graphs. The Turan graph contains no $K_{r+1}$, so every such clique in $J_s(n)$ uses a vertex of $K_{s-1}$. Therefore $J_s(n)$ contains no $s$ vertex-disjoint such cliques, and the extremal number is at least $b_s(n)$.

Induct on $s$, with $s=1$ supplied by the Turan theorem, including its equality characterization. Let $s\ge 2$ and let $G$ be extremal for $s{K}_{r+1}$. The preceding results give $\delta (G)\ge \alpha n-o(n)$ and the $r$-partite subgraph $H$. Keep its classes $H_i$ fixed and assign each of the remaining $o(n)$ vertices to a class in which it has fewest neighbours of a vertex in $H$. Write the resulting classes as $C_i$; all have size $n/r+o(n)$. Choose a positive ${\tau }_n\to 0$ so slowly that ${\tau }_{n}n$ dominates the outside count, every cross-class error in $H$, and every error in the minimum degree of a graph bound.

Suppose some vertex $x\in C_i$ has at least ${\tau }_{n}n$ internal neighbours of a vertex. If $x\notin H$, the assignment rule shows that $x$ has at least ${\tau }_{n}n-o(n)$ neighbours of a vertex in every $H_j$. If $x\in H_i$, it has this many in $H_i$ and $n/r-o(n)$ in the other $H_j$. If $G-x$ contained $s-1$ disjoint $K_{r+1}$, we could choose one vertex in each $N(x)\cap H_j$, successively avoiding those copies and the $o(n)$ missing cross-neighbours of the already chosen vertices. This produces a further $K_{r+1}$ through $x$. For $r=1$, this just chooses an unused neighbour of $x$. Hence $G-x$ is $(s-1)K_{r+1}$-free, and induction givesSince the candidate attains $b_s(n)$, equality holds throughout: $x$ is a universal vertex and $G-x$ is the inductively unique extremal graph. Thus $G$ is isomorphic to $J_s(n)$.

It remains to show that this case must occur. Otherwise all internal vertex degrees are less than ${\tau }_{n}n=o(n)$. Together with the lower bound on $\delta (G)$ and $|C_i|=n/r+o(n)$, this implies that every vertex misses only $o(n)$ vertices outside its own class. If some $C_i$ contains a matching in a graph of $s$ edges, extend its edges one by one to $K_{r+1}$, choosing one vertex from each other class. At every step only $o(n)$ cross-neighbours and boundedly many used vertices are excluded. This gives $s$ disjoint forbidden cliques, a contradiction.

A maximal matching in each class therefore has at most $s-1$ edges, and its at most $2(s-1)$ endpoints form a vertex cover of the internal edges. Their internal vertex degrees are all $o(n)$, so the total internal edge count is $o(n)$. The cross-class edge count is at most $e(T_r(n))$, whenceBut the balanced part sizes of the Turan graph givecontradicting extremality for $s\ge 2$. This argument also works for $r=1$. Consequently, for all sufficiently large $n$,The uniqueness is up to isomorphic graphs, as usual for an extremal graph for disjoint cliques.

Use the usual implicit convention that the infinite connected graph is a locally finite graph. This is needed for the simple random walk and the finite wired constructions to be defined. Choose finite vertex sets $V_1\subset V_2\subset \cdots$ exhausting $V$, with each induced subgraph $G[V_k]$ connected.

For the free uniform spanning forest, sample a uniform spanning tree of $G[V_k]$, using only the internal edges. Its limiting law on edge subsets of $G$ is the free uniform spanning forest measure:The limit is weak convergence of probability measures on $\{0,1{\}}^E$, equivalently convergence of every finite-edge event.

For the wired uniform spanning forest, form $G_k^{\mathrm{w}}$ by identifying every vertex outside $V_k$ to one boundary vertex ${\partial }_k$. Retain all edges with at least one endpoint in $V_k$, preserve parallel edges, and discard loops at ${\partial }_k$. Sample a uniform spanning tree of this finite multigraph and restrict it to the original internal edges. The limiting law isFor each fixed finite set of edges the restriction is unambiguous once $k$ is large. The standard exhaustion theorem guarantees that both limits exist and do not depend on the chosen connected exhaustion. Both are random spanning forests; despite their names, they need not be connected.

On a tree, every finite connected induced subgraph is itself a tree, and its only spanning tree contains all its edges. Thus the free uniform spanning forest is deterministic:Suppose for a contradiction that $G$ is a transient graph. By part (c), choose $e=\{a,b\}$ whose removal leaves two transient graph components $T_a,T_b$. Let $R_a,R_b<\infty$ be their effective resistances to infinity measured from their respective endpoints.

In a wired finite exhaustion, the edge $e$ of resistance one is in parallel with the route from $a$ through $T_a$ to the wired boundary and back through $T_b$ to $b$. The latter route has resistance $R_{a,k}+R_{b,k}$, converging to $R_a+R_b$. Consequently the limiting wired effective resistance isThe edge-inclusion formula for a uniform spanning tree, the one-edge case of the transfer-current theorem, states that an edge of conductance $c_e$ is present with probability $c_e{R}_{\mathrm{eff}}(a,b)$. Passing to the wired limit and using $c_e=1$ givesBut under the free uniform spanning forest, $e$ is present with probability one. This contradicts $\mathrm{WSF}=\mathrm{FSF}$. Therefore the tree is recurrent. Combined with part (b), this characterizes equality of the free and wired uniform spanning forests on locally finite unweighted trees.

WriteLet $G$ be an $H$-free graph on $n$ vertices with $\mathrm{ex}(n,H)$ edges, and choose a uniformly random set of $m<n$ vertices. Its induced subgraph is still $H$-free, and each edge survives with probability $\left(\genfrac{}{}{0ex}{}{m}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Henceso $d_m(H)\ge d_n(H)$. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

If $m=0$, use a single color. Otherwise chooseThe previous bound gives $\mathbb{E}B\le n/4$, including the case $r=0$. By Markov inequality, $\mathbb{P}(B>n/2)\le 1/2$. Sample the hyperplanes, count the monochromatic edges, and repeat if $B>n/2$. The success probability is at least $1/2$, so at most two draws are needed on average.

For a successful draw, select one endpoint of each monochromatic edge and let $D$ be the union of the selected vertices. Then $|D|\le B\le n/2$. Every monochromatic edge meets $D$, so the original colors give a proper graph colouring on the induced subgraph with vertex set $W=V\setminus D$. Since $|W|\ge n/2$, the coloring of all vertices is a semicoloring. This is a random alteration method; no additional colors for $D$ are required.

The number of available colors satisfies $2^r\le 2\max \{1,(4m/n{)}^{{\log }_{3}2}\}$. A simple graph has $m\le n(n-1)/2$, hence semicoloring by independent hyperplanes gives

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

Partition the vertex set into disjoint sets $A$ and $B$ of sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$. The induced subgraph on $A$ has distributionFor $p=n^{-0.9}$,so part (b) shows that $A$ contains a triangle with probability tending to one.

On that event, choose a triangle using only the edges internal to $A$. The edges from its three vertices to $B$ remain independent of this choice. The probability that all $3|B|$ such edges are absent isbecause $p|B|\sim n^{0.1}/2$. Thus, with probability tending to one, some vertex of $B$ is adjacent to a vertex of the triangle. Those four vertices and the four required edges form the given graph $H$, a triangle with an attached leaf in a binomial random graph. Therefore

The hyperplane of a Salvetti complex dual to the loop labelled $v$ is itself the Salvetti complex of the induced subgraph on the neighbours of $v$. If this hyperplane were homeomorphic to a closed surface, its vertex link would be a cycle. Part (c), applied to that induced graph, says that the graph must be one edge. Its Salvetti complex is therefore the two-dimensional torus, a surface of genus one. It cannot be a closed orientable surface of genus two.

A $k$-semicoloring of a finite graph assigns one of $k$ colors to every vertex and is a proper graph colouring on an induced subgraph containing at least half the vertices. This is weaker than a proper coloring of the whole graph, and is useful as an intermediate step in a randomized algorithm.

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.