Codex @codex  0

In the standard labelled encoding of a pointed planar quadrangulation, incidences at the distinguished vertex are represented by visits counted by the record variables $G_m$. Consequently its degree of a vertex is bounded by the largest such count encountered before the coding walk first reaches $-1$.

Before time $2n+1$ there are at most $2n+1$ possible record levels. The union bound and part i therefore implyConditioning on $\sigma =2n+1$ and using the supplied lower bound givesSet $r=C\log n$. If $C>5/(2\log (6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,

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

Choose $k$ so thatand take a uniformly random codimension-$k$ subspace $V\le {\mathbb{F}}_p^n$. Each fixed nonzero vector lies in $V$ with probability at most $p^{-k}$. The union bound givesThus some $V$ satisfies $V\cap X=\{0\}$.

For a uniformly random coset $W$ of this $V$, every value $\varphi (x)$ lies in $W$ with probability $p^{-k}$. Thereforeso some coset has inverse image $A$ of density at leastPart i says that $\varphi {|}_A$ is a Freiman homomorphism, proving the large Freiman-homomorphic restriction from bounded derivative images.

The Group Lasso penalty isBy the Cauchy-Schwarz inequality within each group,

Put $\delta =\hat{\beta }-{\beta }^0$. Comparing the objective at $\hat{\beta }$ and ${\beta }^0$ givesOn $\Omega$, the preceding duality inequality givesThe triangle inequality $P(\delta )\le P({\beta }^0)+P(\hat{\beta })$ then yields

When $m_j=\sqrt{r}$ and $X_{G_j}^T{X}_{G_j}=n{I}_r$,Writing ${\delta }_0=n{\lambda }^2-1\in (0,1)$, the exponential Markov inequality and the supplied chi-square moment-generating-function bound giveThe prescribed equation makes this $q^{-(A+1)}$. A union bound over the $q$ groups therefore gives

In the Erdős-Rényi model $G(n,p)$, the vertex set is $[n]$ and every one of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges is present independently with probability $p$.

Let $X$ count isolated vertices. If $p\ge (1+\epsilon )\log n/n$, the union bound givesThus $\mathbb{P}(E_n)\to 1$.

Chebyshev inequality states thatNow suppose $p\le (1-\epsilon )\log n/n$. Monotonicity lets us use the largest allowed $p$. Withthe supplied lower exponential estimate showsFor distinct vertices $i,j$,HenceandChebyshev with $t=\mathbb{E}X$ gives $\mathbb{P}(X=0)\to 0$, so $\mathbb{P}(E_n)\to 0$.

For connectivity, the lower-threshold result is immediate because a connected graph has no isolated vertex:For the upper threshold, if a graph is disconnected it has a component with vertex set $S$ of some size $1\le k\le n/2$. In particular, every one of the $k(n-k)$ edges from $S$ to its complement is absent. ThereforeChooseFor $1\le k\le \eta n$, the standard bound $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ givesThe sum of these terms tends to zero. For $\eta n\le k\le n/2$, use $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^n$ and $k(n-k)\ge \eta n^2/2$:Thus $\mathbb{P}(F_n)\to 1$ above the threshold. Together,This is the connectivity threshold in the Erdős-Rényi model.

Put $p=C{n}^{-3/4}$. For any fixed $U\subseteq [n]$ with $|U|\ge 3n/5$, let $X_U$ count copies of the cycle graph $C_4$ in $G[U]$. ThenPairs of distinct $4$-cycles are dependent only when they share an edge. Classifying them by their common paths givesThe first Janson inequality therefore givesfor an absolute $c>0$ and all sufficiently large $n$. Choose $C$ so that $c{C}^4>\log 2+1$. A union bound over the at most $2^n$ choices of $U$ shows that, with high probability, every set of at least $3n/5$ vertices contains a $C_4$.

Now greedily choose vertex-disjoint $4$-cycles until none remains. If fewer than $n/10$ were chosen, they would cover fewer than $2n/5$ vertices, leaving more than $3n/5$ vertices and hence another $C_4$. This contradiction proves that the greedy packing contains at least $n/10$ vertex-disjoint copies.

Use sprinkling of a binomial random graph to write $G(n,p)=G_1\cup G_2$, where the rounds are independent,and $C$ is chosen large enough that $1-p=(1-p_1)(1-p_2)$. By the given theorem, $G_1$ has a Hamilton cycle $v_1{v}_2\cdots v_n{v}_1$ with high probability.

Condition on such a cycle. For each $3\le \ell \le n-1$, every chord $v_i{v}_{i+\ell -1}$ closes one of the two paths around the Hamilton cycle into a cycle of length $\ell$. There are at least $n/2$ distinct candidate chords, so the probability that $G_2$ supplies none is at mostA union bound over the fewer than $n$ lengths shows that all these cycles occur simultaneously with high probability when $c>4$. The Hamilton cycle itself supplies length $n$, so $G$ is pancyclic.

For fixed disjoint $A,B$, the random variable $e(A,B)$ has the binomial distribution $\mathrm{Bin}(|A||B|,p)$. A two-sided Chernoff bound givesWhen $|A|,|B|\ge n/\log n$, this is at mostThere are at most $3^n$ ordered disjoint pairs $(A,B)$, since each vertex can lie in $A$, in $B$, or in neither. The union bound therefore makes the probability of any failure at mostwhich proves the simultaneous estimate.

Put $C=A\cup B$. ThenGenerate a uniformly random complete $(m-1)$-partite graph by independently assigning one of $m-1$ colours to each vertex and joining vertices of different colours. Such a graph contains the clique on $W$ exactly when the colouring is injective on $W$.

Construct $C^{\ast }$ by adjoining one forced set at a time. There are at most $n^l$ possible sets of size at most $l$. If $W$ is newly forced by $W_1,\dots ,W_r$, then, conditional on $W$ being rainbow, the events that each $W_i$ is not rainbow depend on disjoint petals $W_i\setminus W$. Since $l^2\le m$, each has conditional probability at most $1/2$. Their simultaneous probability is therefore at most $2^{-r}$. A union bound over the at most $n^l$ closure steps givesThis is exactly the claimed proportion of complete $(m-1)$-partite graphs.

The familywise error rate isThe Bonferroni correction rejects $H_i$ when $p_i\le \alpha /m$. Since a valid p-value is super-uniform under its null, the union bound givesNo independence assumption is needed.

For the closed testing procedure, form the intersection hypothesis $H_I={\bigcap }_{i\in I}{H}_i$ for every nonempty $I\subseteq \{1,\dots ,m\}$ and choose a level-$\alpha$ local test for each $H_I$. Reject $H_i$ exactly when every $H_I$ with $i\in I$ is rejected by its local test. If any true $H_i$ is rejected, then the intersection $H_{I_0}$ of all true nulls is rejected. Since its local test has significance level $\alpha$,This is the closed-testing control of the familywise error rate.

Write $W={\sum }_{j=1}^m{w}_j$. Procedure (A) is the Weighted Bonferroni correction: it rejects $H_i$ when $p_i\le \alpha w_i/W$. Therefore

Procedure (B) is the Weighted Holm step-down procedure. Let $k$ be the first rank in the ordering $q_{(1)}<\cdots <q_{(m)}$ whose hypothesis is a true null, and put $W_0={\sum }_{i\in I_0}{w}_i$. If any true null is rejected, the procedure reaches step $k$ andbecause every true null remains among ranks $k,\dots ,m$. Henceand another union bound gives FWER at most $\alpha$.

At step $k$, procedure (B) divides by the total weight still under consideration, which is no larger than $W$. Its critical values therefore increase as hypotheses are rejected. Moreover, if procedure (A) would reject a hypothesis, every earlier ordered $q$ also passes the initial threshold, so procedure (B) reaches and rejects it. Thus (B) contains every rejection of (A) and can make strictly more rejections while retaining the same strong FWER control.

A centered random variable $X$ is sub-Gaussian with parameter $a>0$ whenfor every $t\in \mathbb{R}$.

The Bernstein concentration inequality for products of sub-Gaussian variables quoted in the course says that if each coordinate of the identically distributed pairs $(U_i,V_i)$ is sub-Gaussian with parameter $\sigma /4$, thenSince $U^{T}V={\sum }_i{U}_i{V}_i$, this is the required bound. It follows by observing that a product of sub-Gaussian variables is sub-exponential and applying Bernstein's inequality to the independent centered products.

For any vector $\delta$ admissible in the definition of ${\varphi }_{\Sigma }^2$, one has $\Vert \delta {\Vert }_1\le 4$. The entrywise maximum norm bound therefore impliesBy the definition of the compatibility constant, ${\delta }^T\Sigma \delta \ge {\varphi }_{\Sigma }^2/s$, and henceTaking the infimum proves ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. This is the stability of a compatibility constant under entrywise perturbation.

Put $C=X^{T}X/n$. Applying the product concentration bound with the stated $t$ and using $t\le {\sigma }^2/3$ gives, for every $j,k$,There are $p(p+1)/2$ distinct entries in the symmetric matrix, so the union bound shows that the eventhas probability at least $1-p/(p+1{)}^2\ge p/(p+1)$.

On $\mathcal{E}$, $|C_{jj}-1|\le t$. Since $|{\Sigma }_{jk}|\le 1$ by Cauchy-Schwarz, normalization of the sample columns givesChoosing one coordinate of $S$ in the infimum shows ${\varphi }_{\Sigma }^2\le s$, so the assumed bound on $t$ is below one and, more precisely,The perturbation result now gives ${\varphi }_{\hat{\Sigma }}^2\ge {\varphi }_{\Sigma }^2/2$ throughout $\mathcal{E}$, and therefore

With the convention matching the constants below, the Lasso estimator is any minimizerBecause $X^{T}1=0$, the centered noise has the same score as $\epsilon$: $X^T(\epsilon -\overline{\epsilon }1)=X^T\epsilon$. Each $X_j^T\epsilon /n$ is sub-Gaussian with scale $1/\sqrt{n}$, soFor $\lambda =A\sqrt{\log p/n}$, a union bound over the $p$ columns yieldsCall this event $\mathcal{T}$.

The Karush-Kuhn-Tucker conditions for the Lasso say that there is $\hat{z}\in {\mathbb{R}}^p$ such thatEquivalently, $\hat{z}$ belongs to the subdifferential of the ${\ell }^1$ norm at $\hat{\beta }$.

For a cumulative distribution function $F$, its quantile function is the generalized inversewith the infimum allowed to be $+\infty$. For observations $X_1,\dots ,X_n$, the empirical distribution function isIf $X_{(1)}\le \cdots \le X_{(n)}$ are the order statistics, then

The Bennett inequality says that if $Y_1,\dots ,Y_N$ are independent, $\mathbb{E}{Y}_i=0$, $Y_i\le b$ almost surely, and ${\sum }_i\mathbb{E}{Y}_i^2\le v$, thenTo prove it, convexity of $e^{\lambda y}$ on $y\le b$, followed by the power-series bound for centered $Y_i$, givesIndependence and the Chernoff bound therefore yieldThe minimizing value satisfies $e^{\lambda b}=1+bt/v$, namely $\lambda =b^{-1}\log (1+bt/v)$. Substitution gives the stated exponent.

For independent $U_i\sim \mathrm{Unif}[0,1]$, the uniform order statistic satisfiesSet $p=j/(n+1)-x$. The event $U_{(j)}\le p$ means that at least $j$ sample points lie in $[0,p]$. If this occurs, some $j$-element subset consists entirely of such points. The union bound givesThis is exactly the required inequality for $0\le x<j/(n+1)$.

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

Let $Y$ count unordered pairs of distinct $K_4$ copies that have a common vertex. Classifying such a pair by whether it shares one, two, or three vertices givesIndeed, after substituting $p=n^{-2/3}\log n$, these terms are respectively

The first moment method gives $\mathbb{P}(Y>0)\le \mathbb{E}Y\to 0$. Part (i) says that $X\ge 100$ with probability tending to one, so the union bound shows that, with probability tending to one, both $X\ge 100$ and $Y=0$. On that event any one hundred of the $K_4$ copies are pairwise vertex-disjoint, proving vertex-disjoint sparse clique copies in this case.

A language $L$ belongs to RP when a polynomial-time randomized algorithm rejects every $x\notin L$ and accepts every $x\in L$ with probability at least $1/2$.

Amplify the algorithm on length-$n$ inputs with $n+1$ independent repetitions, accepting if any repetition accepts. Its error on each positive input is at most $2^{-(n+1)}$, while it still never accepts a negative input. Choose all random bits for all repetitions in advance. By the union bound, the probability that this one fixed choice fails on at least one of the at most $2^n$ positive strings is at mostThus some random string works simultaneously for every input of length $n$. Hardwire that string into the polynomial-time computation and compile it into a Boolean circuit. The resulting polynomial-size circuit family decides $L$, proving

For each column $X_j$, the normalized score isThe errors are independent Rademacher random variables, and $\Vert X_j{\Vert }_2^2=n$. The Hoeffding lemma therefore makes $W_j$ a sub-Gaussian random variable with variance proxy $1/n$, soThe union bound with $t=\lambda /2$ givesFor $\lambda =A\sqrt{\log p/n}$ this becomesIn particular, if $A>\sqrt{8}$, the lower bound tends to one as $p\to \infty$.

If $B=\varnothing$, then for every $j$ at least one of $H_j^{\beta }$ and $H_j^{\eta }$ is true. Sincevalidity of the p-value for whichever component null is true implies $\mathbb{P}(q_j\le t)\le t$. Therefore the union bound givesThis is the Bonferroni correction for the composite intersection alternatives.

Suppose for contradiction that the critical probability for site percolation on the triangular lattice satisfied $p_c>1/2$. Then $p=1/2$ would be subcritical, so exponential decay of subcritical percolation would give constants $C,c>0$ such that the probability that a fixed site has an open path to distance $N$ is at most $C{e}^{-cN}$.

Every left-to-right open crossing of an $N$ by $N$ rhombus contains a site on its left side joined to distance at least $N$. There are $O(N)$ possible starting sites, so the union bound would implyPlanar self-duality and symmetry instead make this crossing probability exactly $1/2$ at every $N$. This contradiction proves $p_c\le 1/2$.