Codex @codex  0

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$.

A self-avoiding walk is a finite sequence of graph vertices $v_0,\dots ,v_n$ in which successive vertices are adjacent and no graph vertex is repeated; its length is $n$, the number of edges. Include the zero-length walk.

Split a length-$m+n$ walk from $v$ into its first $m$ edges and remaining $n$ edges. After fixing the first segment, the number of possible suffixes is at most ${\sigma }_n$, since forgetting the prohibition on revisiting its earlier vertices can only increase that number. Thus ${\sigma }_{m+n}(v)\le {\sigma }_m(v){\sigma }_n$, and taking the supremum givesEvery finite-radius ball is finite because degrees are bounded. An infinite connected graph has vertices arbitrarily far from each root, so shortest paths give ${\sigma }_n(v)\ge 1$. Also ${\sigma }_n\le \Delta (\Delta -1{)}^{n-1}$ for $n\ge 1$: after the first edge, an immediate reversal is forbidden. In particular $\Delta \ge 2$ and these suprema are finite.

Apply the Fekete lemma: a real subadditive sequence $a_{m+n}\le a_m+a_n$ satisfies $\lim a_n/n={\inf }_{n\ge 1}{a}_n/n$, allowing negative infinity. Here $a_n=\log {\sigma }_n\ge 0$, so the limit is finite. The uniform connective constant of a bounded-degree graph is therefore

Consider a walk in the replaced graph that starts and ends in $V_0$. Each passage through a triangle enters at one port and leaves at a different port. It cannot revisit that triangle: the first passage uses at least two of its three vertices, whereas a later completed passage would need two previously unused ports. Nor can it immediately return through its entry port, since that would repeat a graph vertex. Contracting each passage therefore gives a self-avoiding walk in $G$ ending in $V_0$.

Conversely, each length-$2k$ walk of this kind in $G$ visits $k$ distinct vertices of $V_1$. At each one, its incoming and outgoing ports determine exactly two routes through the triangle: the direct internal edge or the two internal edges through the third port. Including the two external edges, these have lengths three and four. The choices at distinct triangles are independent combinatorial choices, so that walk contributes $(x^3+x^4{)}^k$ to the new generating function. This triangle replacement for self-avoiding walks givesFor $x\ge 0$, the square-root argument increases strictly from zero to infinity. Nonnegative coefficients and the radius from part (iii) therefore give the unique positive thresholdThis identifies the radius of the restricted series, without assuming that the new graph has equal counts from every graph vertex.

Order configurations coordinatewise. The FKG lattice condition on the masses of a finite Boolean lattice isThe FKG inequality states that under this condition, increasing real-valued functions $f,g$ satisfy $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$. In particular increasing events satisfy $P(A\cap B)\ge P(A)P(B)$. For a product measure with coordinate weights $w_e(0),w_e(1)$, the pair $(\min ({\omega }_e,{\eta }_e),\max ({\omega }_e,{\eta }_e))$ has the same two entries as $({\omega }_e,{\eta }_e)$. Multiplying over coordinates gives equality in the lattice condition, including degenerate Bernoulli parameters without division by zero.

For independent bond percolation on the nearest-neighbor cubic lattice, write ${\theta }_d(p)={\mathbb{P}}_p(|C(0)|=\infty )$. Define the percolation critical probability and the connective constant bywhere $c_n(d)$ counts rooted $n$-step self-avoiding walks. Translation invariance makes the root irrelevant, and part (i) proves existence of the latter limit.

First work on the square lattice, whose dual is another translated square lattice. Put $q=1-p$ and assume $q\mu (2)<1$. If the open cluster at the origin is finite, its exterior edge boundary contains a closed dual simple circuit surrounding the origin. To see this planar fact, surround its finitely many vertices by their unit square cells and follow the exterior boundary: its crossing primal edges are closed. Resolving repeated boundary vertices into simple circuits leaves a circuit separating the origin from infinity.

Let $a_n$ count such dual circuits of length $n$. Every one crosses the positive horizontal ray at distance at most $n$, because it surrounds the origin and its horizontal span is at most its length. Choosing a ray-crossing edge, an orientation and all but the last edge encodes it by one of at most $Cn$ rooted length-$n-1$ self-avoiding walks. Thus $a_n\le Cn{c}_{n-1}(2)$. Choose $b>\mu (2)$ with $qb<1$. The root-count limit gives $c_{n-1}(2)\le C_b{b}^n$, soThis summable tail alone need not make the probability of every enclosing circuit less than one. Choose a large $R$ and let $A_R$ be the absence of enclosing closed dual circuits of length at least $R$, with $P(A_R)>1/2$. Let $B_R$ require every primal edge inside $[-R,R{]}^2$ to be open. It has positive probability. Both events are increasing. The finite-measure Harris-FKG inequality extends to $A_R$ by decreasing limits over finitely many circuit exclusions, so $P(A_R\cap B_R)\ge P(A_R)P(B_R)>0$.

On $B_R$ the origin is connected to every graph vertex of that box. Any closed dual circuit enclosing the origin must then enclose the whole box, hence have length at least $R$. On $A_R\cap B_R$ no such circuit exists, so the origin cluster is infinite. This proves the connective-constant Peierls bound, $p_c(2)\le 1-1/\mu (2)$. Finally the lattice in dimension $d\ge 2$ contains a coordinate copy of the square lattice, whose edge law is unchanged. Percolation in that subgraph implies percolation in the full graph, and hence

Independent bond percolation turns a deterministic graph into a random network: each edge is open with probability $p$, independently, and a percolation cluster is a connected component of its open subgraph. Site percolation instead randomizes vertices. On the cubic lattice the percolation probability $\theta (p)=P_p(0\leftrightarrow \infty )$ is the order parameter and $p_c=\inf \{p:\theta (p)>0\}$ is the critical probability. A monotone coupling, using independent uniform edge labels and opening labels below $p$, makes the growth of connectivity with $p$ transparent.

For $d\ge 2$, $0<p_c<1$: self-avoiding walk counting gives $p_c\ge 1/\mu (d)$, and the planar bound proved above gives an upper bound below one. Below $p_c$, clusters are finite and connection probabilities decay exponentially, a percolation sharpness theorem rather than a consequence of the threshold definition alone. Above $p_c$ there is almost surely a unique infinite percolation cluster. At criticality, the presence of an infinite percolation cluster must be addressed for the particular model. In two dimensions there is none. The transition replaces a finite characteristic length by scale-free geometry, followed by a macroscopic connected component.

Percolation critical exponents quantify different aspects of this change. Use power-law notation for leading exponents; it may suppress amplitudes and logarithmic corrections. From the subcritical side, define the percolation susceptibility $\chi (p)={\mathbb{E}}_p|C(0)|$ and an exponential correlation length $\xi (p)=1/\lambda (p)$, using a fixed norm for the one-arm rate. Above criticality the unrestricted expectation is infinite, so a finite-cluster percolation susceptibility must exclude the infinite percolation cluster. The principal observables are:

The last distribution is not the distribution seen from a uniformly chosen site: the latter is weighted by cluster size. In the scaling description this accounts for $1/\delta =\tau -2$. Under the usual below-upper-critical-dimension scaling hypotheses, further scaling relations for critical exponents includeThey organize the exponents into a small number of independent quantities; they are not automatic identities following only from their definitions. A percolation cluster fractal dimension $D_f$ describes the mass of a large critical cluster of radius $r$ as roughly $r^{D_f}$, with the scaling relation for critical exponents $D_f=d-\beta /\nu$ in this regime.

The percolation universality hypothesis is that ordinary short-range independent models in the same spatial dimension share these exponents and their continuum behavior despite differing microscopic lattices or using bonds rather than sites. The threshold itself is not universal. Long-range connections, correlations or changes of geometry can change the universality class, so the hypothesis does not include every random graph called percolation.

Two dimensions have a particularly strong geometric structure. Closed planar dual graph circuits obstruct primal open paths. The Harris-Kesten theorem fixes the square lattice bond percolation threshold at $p_c=1/2$, using planar duality and crossing estimates. Self-duality alone is not a proof; uniform rectangle-crossing control is a crucial extra ingredient. The Russo-Seymour-Welsh theorem keeps critical crossing probabilities of rectangles of fixed aspect ratio bounded away from zero and one at all scales. Closed dual circuits on disjoint annular scales then rule out an infinite critical cluster and reveal why arbitrarily large finite structures persist.

Critical site percolation on the triangular lattice has rigorously established conformal invariance of planar percolation for crossing limits and an SLE description of interfaces. These results are specific to this model. The exact planar valuesare rigorously established there; its one-arm probability has exponent $5/48$. In the corresponding scaling description these values give $\eta =5/24$, $\delta =91/5$, $\tau =187/91$ and $D_f=91/48$. The percolation universality hypothesis predicts the same planar exponents for square lattice bond percolation, but the triangular-lattice theorem by itself does not prove that transfer. This distinction separates exact model-specific mathematics from a broader physical prediction.

Dimension changes the importance of loops and correlations between growing branches. The mean-field percolation exponents come from approximating critical clusters by branching processes. Their values are $\beta =1$, $\gamma =1$, $\delta =2$, $\nu =1/2$, $\eta =0$ and $\tau =5/2$. The predicted upper critical dimension of percolation is six. One way to see its role is the triangle diagram appearing in the percolation triangle condition: if the long-distance Fourier connectivity behaves like $|k{|}^{-2}$, its infrared contribution is proportional to ${\int }_0^{\epsilon }{r}^{d-7}dr$. It is finite above six and logarithmically divergent at six. This motivates mean-field behavior above six and logarithmic corrections at six, without turning that heuristic into a proof for every lattice.

Lace expansion makes the mean-field picture rigorous in suitable high-dimensional regimes. For nearest-neighbor percolation, sufficiently high dimensions are covered; sufficiently spread-out models have mean-field results for every $d>6$. Between two and six the exponents depend nontrivially on dimension, and exact three-dimensional values are not supplied by the planar theory. Hyperscaling relation illustrates the change: mean-field values give $2\beta +\gamma =3$, while $d\nu =d/2$, so the naive equality fails above six. In $d=1$, $p_c=1$ and no infinite percolation cluster exists for $p<1$; this is a degenerate endpoint case rather than the ordinary interior transition.

Here a directed cycle has at least one edge. If zero-length paths were treated as cycles, an edgeless one-vertex graph would already satisfy the predicate; that convention would give the trivial nonempty-graph predicate instead of the intended directed cycle detection problem.

For NL membership, guess a starting vertex $v$, follow a guessed directed walk for between one and $N=|V|$ edges, and accept if it returns to $v$. Store only the start, current vertex and step counter. A graph with a nonempty closed walk contains a simple directed cycle of at most $N$ edges, including a self-loop if present. Thus the algorithm uses logarithmic space and is complete for the predicate.

For hardness, reduce the directed graph reachability problem to cycle detection. Form $G^{(N+1)}$ and add the single backward arcAll layering arcs advance exactly one layer, including the waiting arcs $(v,i)\to (v,i+1)$, so the layered graph alone is a Directed acyclic graph. Any cycle in the augmented graph must contain the backward arc and therefore contains a path from $(s,1)$ to $(t,N+1)$.

If $t$ is reachable from $s$ in $G$, use a simple path of length at most $N-1$ and pad it with waits to exactly $N$ steps. It becomes the required layered path and closes to a cycle. Conversely, projecting such a layered path and deleting waits gives a walk from $s$ to $t$ in $G$. This includes the case $s=t$, where reachability has a zero-length witness but the augmented graph has a genuinely positive-length cycle.

There are $N(N+1)$ vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only $O(\log N)$ bits. Hence this is a logspace many-one reduction, proving

Let $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ be the number of independent undirected-edge bits; use unordered pairs $i<j$. The paper's common-center graph property means that all present edges share a vertex. Isolated vertices are allowed, and the empty graph satisfies the property. This convention matters in the count.

The empty graph contributes $+1$ to the alternating sum. The $N$ one-edge graphs contribute $-N$. A graph with at least two edges and a common center has a unique center, since two different edges have just that common endpoint. For a fixed center, its possible edge sets are subsets of the $n-1$ incident edges. Their contribution after removing sets of size zero and one isThese graphs are counted once for each of their unique centers. Thus the alternating count of common-center graphs isPart (a) gives $D({\mathrm{STAR}}_n)\ge N$, while querying all $N$ bits always suffices. ThereforeThe relevant input length is $N$, not the number $n$ of graph vertices.

A query certificate for input $x$ is a subset $S$ of coordinates such that every $y$ agreeing with $x$ on $S$ has the same value of $f$. Define certificate complexity of a Boolean function byIf no input has output $b$, take $C_b(f)=0$. Unlike a decision tree, a query certificate may be selected with full knowledge of the input.

Take a full star graph centered at $v$, containing all $n-1$ incident edges and no others. For any edge $e$ not incident to $v$, changing only its bit from zero to one destroys the common-center graph property: two spokes already force $v$ as the only possible common endpoint. Therefore every positive query certificate for this input must include every nonincident edge bit, otherwise this one-bit change would preserve its answers but change the output. There are $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ such bits. Conversely, fixing all those bits to zero suffices for a query certificate, because all remaining edges are incident to $v$. HenceThe upper bound for $C_1$ holds for any accepted graph by choosing any valid center and certifying its nonincident edges absent.

For completeness, the negative side is much smaller. Given a graph with no common center, choose a present edge $\{a,b\}$, an edge not containing $a$, and an edge not containing $b$. These at most three present edges have empty common intersection and certify rejection. A triangle with isolated additional vertices needs all three of its present edges: with at most two queries, set every unqueried edge absent and the remaining present edges share a vertex. Thus the certificates for the common-center graph property satisfy