Codex @codex  0

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 strong law of large numbers states that if $(X_i{)}_{i\ge 1}$ are independent and identically distributed random variables with $\mathbb{E}|X_1|<\infty$, thenalmost surely. Under the stronger fourth-moment hypothesis, it has a short proof. Put $\mu =\mathbb{E}{X}_1$, $Y_i=X_i-\mu$, and $S_n={\sum }_{i=1}^n{Y}_i$. Independence and centering make every term in the expansion of $S_n^4$ vanish unless each index occurs at least twice, soFor every $\epsilon >0$, the Markov inequality givesThe probabilities are summable, so the first Borel-Cantelli lemma says that $|S_n|>\epsilon n$ occurs only finitely often almost surely. Apply this simultaneously to $\epsilon =1,1/2,1/3,\dots$ to obtain $S_n/n\to 0$ almost surely, which is the claimed law.

The Chebyshev inequality states that for a random variable $Y$ with finite variance and every $\delta >0$,Indeed, Markov inequality applied to the nonnegative variable $(Y-\mathbb{E}Y{)}^2$ gives

The sum $S_n=X_1+\cdots +X_n$ has the binomial distribution, soFor fixed $n$ this is a finite sum of polynomial functions of $p$, hence is a polynomial.

The Markov inequality applied to the first exponential-moment bound givesThe second bound controls the lower tail. The union bound therefore givesSinceputting $L=\log (2/\delta )$,makes the exponent equal to $-L$. It follows that the Catoni mean estimator satisfies

By Tonelli theorem for the nonnegative indicators,If this is finite, then $N$ is finite almost surely: alternatively, Markov inequality givesSince $\{N=\infty \}\subseteq \{N\ge m\}$ for every $m$,This is the first Borel-Cantelli lemma.

For a nonnegative random variable $Y$ and $a>0$, the Markov inequality isIndeed, $Y\ge a{1}_{\{Y\ge a\}}$ pointwise. Taking expectations and dividing by $a$ proves the claim.

Markov inequality says that a nonnegative random variable $Y$ satisfiesChebyshev inequality says that a random variable with finite variance satisfies

Let $X$ count triangles in $G(n,p)$. The triangle count in a binomial random graph calculation givesSince $p\gg n^{-1}$,For sufficiently large $n$, $\mu >200$, and Chebyshev inequality gives

Conditional on the covariates and all responses used to construct $\hat{g}$, the residual ${\epsilon }_i$ has conditional second moment at most $C$; conditional independence under the null is what permits this conditioning. ConsequentlyThe Markov inequality proves

Next, the Cauchy-Schwarz inequality givesThe first factor converges to zero in probability. The weak law of large numbers and part a make the second $O_p(1)$, so the product converges to zero in probability.

Fix $k\ge 1$ and sample $G$ from the Erdős-Rényi model with $p=\frac{1}{2}{n}^{-2/3}$. Let $X$ count copies of the complete bipartite graph $K_{3,3}$. By the expected subgraph count in the Erdős-Rényi model,

Put $m=\lceil n/k\rceil$ and let $Z$ count independent set of size $m$. If the chromatic number satisfies $\chi (G)\le k$, some colour class has at least $m$ vertices, so $Z\ge 1$. Moreover,because the positive part of the exponent is $O(n)$ whereas $p\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ has order $n^{4/3}$. The first moment method therefore gives $\mathbb{P}(\chi (G)\le k)\le \mathbb{E}Z=o(1)$.

Using Markov inequality for $X$ and the union bound,for all sufficiently large $n$. Hence at least one such $G$ contains no $K_{3,3}$ and has $\chi (G)>k$.

With $p=c\log n/n$, the inequality $1-p\le e^{-p}$ giveswhen $c>1$. The Markov inequality now givesConsequently the upper side of the isolated-vertex threshold in the Erdős-Rényi model is

The Markov inequality states that for a nonnegative random variable $Y$ and $a>0$,For $t>0$, the event $X\ge x$ is the same as $e^{tX}\ge e^{tx}$. Applying Markov's inequality to the nonnegative variable $e^{tX}$ gives the exponential Markov bound

First suppose $L\in \mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Run the RP algorithm for $L$ and the RP algorithm for its complement with fresh random bits. If the first accepts, output one; if the second accepts, output zero; otherwise repeat. Neither output can be wrong, and on every input the appropriate algorithm accepts in each round with probability at least $1/2$. The number of rounds is dominated by a geometric distribution of mean two, so this is an always-correct algorithm with polynomial expected running time.

Conversely, let $T$ be always correct when it halts and have expected running time at most $p(n)$. Run it for $2p(n)$ steps. Markov inequality givesAccept exactly when $T$ halts and outputs one; this is an RP algorithm for $L$. Accepting exactly when it halts and outputs zero is an RP algorithm for the complement. Thereforeis equivalent to zero-error expected polynomial time.

For $z=x+iy$ with $|x|\le 1$ and $0<y\le 1$, the given Reverse SLE derivative martingale starts fromIt is a nonnegative local martingale and therefore a supermartingale. Since its second factor is at least one,

Choosewhich is possible exactly because $\kappa >8$. At height $y_n=2^{-n}$, take a horizontal grid of spacing comparable to $y_n$ in $[-1,1]$. The Markov inequality gives, at each grid point,There are $O(y_n^{-1})$ grid points, so the probability that the bound fails anywhere on level $n$ is at most $C{y}_n^{1-2\alpha -8/\kappa }$. These probabilities are summable. The Borel-Cantelli lemmas therefore give an almost surely finite random constant controlling every sufficiently fine grid, and enlarging it handles the finitely many remaining levels.

Every point of the half-rectangle lies within a fixed hyperbolic distance of one of these grid points at comparable height. The Koebe distortion theorem compares the two derivatives by a universal factor. Hence an almost surely finite random $C$ satisfiesfor all $x\in [-1,1]$ and $0<y\le 1$. This proves the Reverse SLE derivative bound above the space-filling threshold.

Let $E_n$ and $E$ be the projection-valued measures of $A_n$ and $A$. Using the projection $P_n:\mathcal{H}\to {\mathcal{H}}_n$, defineThe scalar spectral measures converge weakly whenfor every bounded continuous function $f$ and every $v,w\in \mathcal{H}$. By the spectral theorem for normal operators on a separable Hilbert space, this is equivalent to

The assumed moment identities say precisely that this convergence holds for every monomial $f(x)=x^m$. It follows by linearity for every polynomial. For $v=w$, the $m=2$ identity givesso Markov inequality makes the positive measures $({\mu }_v^{(n)})$ tight. Higher even moments similarly control the tails of any fixed polynomial.

Given a bounded continuous $f$ and $ϵ>0$, choose $R$ so that the measure tails are uniformly small. The Weierstrass approximation theorem supplies a polynomial $p$ withMoment convergence handles $p$; tightness and a sufficiently high even moment handle the two tails. Hence $\int fd{\mu }_v^{(n)}\to \int fd{\mu }_v$. The polarization identity then gives the same conclusion for ${\mu }_{v,w}^{(n)}$. This proves weak convergence of scalar spectral measures.

The assertion fails if only $m=1$ is assumed. Let $\mathcal{H}={\ell }^2(\mathbb{N})$, let ${\mathcal{H}}_n=\mathrm{span}\{e_1,\dots ,e_n\}$, take $A=0$, and letThe reversal matrices are self-adjoint unitaries. For fixed $v,w\in {\ell }^2$,because the finite head of one vector is paired with the vanishing tail of the other. Thus the $m=1$ condition holds. However, $A_n^2=I_{{\mathcal{H}}_n}$, soin general. Taking $f(x)=x^2$ shows that the spectral measures do not converge weakly.

Choose $0<\alpha <\epsilon /p$. At dyadic level $m$, Markov inequality and a union bound giveuniformly in $n$. Summing over $m$ shows that, outside a set of probability at most $C_0{C}^{-p}$, all dyadic increments obey this bound. Chaining dyadic approximations and using continuity givesfor all $s,t$. Since $X_0^n=0$, the paths then lie in the stated compact Hölder set by the Arzela-Ascoli theorem. Taking $C$ large proves tightness.

Markov inequality gives $\mathbb{P}(T>0)\le \mathbb{E}T=O(n^{3-3\alpha })\to 0$ when $\alpha >1$.

Letwhere the positive constant $c$ will be chosen small, and sample the binomial random graph $G(N,p)$. If $X$ counts its copies of $C_4$, thenIf $Y$ counts its independent $k$-sets, thenHere $pk\sim c^{-3/4}\log k$. Choosing $c$ sufficiently small makes the negative exponential term dominate $k\log (eN/k)$, so $\mathbb{E}Y=o(1)$. By Markov inequality, with positive probability $X<N/2$ and $Y=0$.

Starting from such a graph, delete one vertex from each remaining $C_4$. This random alteration method removes fewer than $N/2$ vertices, destroys every $C_4$, and cannot create an independent set of order $k$. The resulting graph has at least $N/2$ vertices, so its edges and nonedges give a red-blue colouring with neither a red $C_4$ nor a blue $K_k$. Consequently

For $A\in {\mathcal{F}}_n$, the defining identity for $X_{n+1}$ givesPart (b) therefore identifies $X_n$ with $\mathbb{E}[X_{n+1}\mid {\mathcal{F}}_n]$, so $(X_n,{\mathcal{F}}_n)$ is a martingale.

The atom formula also provesLet $B_{n,K}=\{|X_n|>K\}$. Then $\mathbb{P}(B_{n,K})\le \mathbb{E}|X|/K$ by Markov inequality, whileThe uniform absolute continuity for a finite measure makes the right-hand side uniformly small as $K\to \infty$. Thus $(X_n)$ is uniformly integrable. The Martingale convergence theorem now supplies an integrable random variable $Y$ such that $X_n\to Y$ both almost surely and in $L^1$.

Fix a deterministic horizon $T$ and $\epsilon >0$. For every localization index $N$,by Markov inequality. Because $T_N\uparrow \infty$ almost surely, the first term tends to zero as $N\to \infty$. For fixed $N$, the second tends to zero as $n\to \infty$. Taking first the limit superior in $n$ and then $N\to \infty$ provesin probability. This is precisely uniform convergence on compacts in probability.

Let the energy of a flow be $\mathcal{E}(\theta )={\sum }_e\theta (e{)}^2$, with each unoriented edge counted once. Expanding as in part (i), dropping orientation signs, and summing over common edges givesuniformly in $r$.

Part (i), $\mathbb{E}{X}_r=1$, and the Paley-Zygmund inequality give a constant $a>0$ such that $\mathbb{P}(X_r>1/2)\ge a$ for every $r$. The preceding uniform expectation bound and Markov inequality allow a constant $L$ such thatOn this event, ${\theta }_{\omega }/X_r$ is a unit open flow from $o$ to $z_r$ with energy at most $4L$.

The events that there is such a bounded-energy unit flow from $o$ out of $B(o,r)$ are decreasing in $r$. Their intersection still has probability at least $a/2$. A diagonal compactness argument produces on this intersection a unit flow from $o$ to infinity, supported on its open cluster, with finite energy. The finite-energy flow criterion for transience makes that open cluster transient.

Thus a transient open cluster exists with positive probability. This existence event is a tail event: changing finitely many edges cannot destroy transience in every infinite component, because transience is invariant under finite graph modifications. The Kolmogorov zero-one law upgrades its probability to one.