Asymptotic quantifiers and uniform parameter ranges

Let $S$ be an unbounded subset of the natural numbers. All limits below are taken as $n\to \mathrm{\infty }$ through $n\in S$: $x_n\to L$ means that for every $\epsilon >0$ there is an $N$ such that $\mathrm{\mid }{x}_n-L\mathrm{\mid }<\epsilon$ for every $n\in S$ with $n\ge N$. A property holds eventually if it holds for all such $n$ beyond some $N$.

For real deterministic sequences $a_n,b_n$ with $b_n>0$ eventually, $a_n=o(b_n)$ means that for every $\epsilon >0$ there is an $N$ such that $\mathrm{\mid }{a}_n\mathrm{\mid }\le \epsilon b_n$ for all $n\in S$ with $n\ge N$. The notation $a_n=O(b_n)$ means that there are constants $C>0$ and $N$ such that $\mathrm{\mid }{a}_n\mathrm{\mid }\le C{b}_n$ for all $n\in S$ with $n\ge N$.

For each $n\in S$, let $({\mathrm{\Omega }}_n,{\mathcal{F}}_n,{\mathbb{P}}_n)$ be a probability space and $E_n\in {\mathcal{F}}_n$ an event. The events $E_n$ hold with high probability if ${\mathbb{P}}_n(E_n)\to 1$. The spaces may vary with $n$; in the finite outcome-weight model $(\mathrm{\Omega },w)$, every subset of $\mathrm{\Omega }$ is an event and its probability is the sum of its outcome weights.

Suppose that for each $n\in S$ a parameter $p$ ranges over a set $I_n$, and that $a_n(p)$ and $b_n(p)>0$ are real-valued on that set. The assertion $a_n(p)=O(b_n(p))$ uniformly over $p\in I_n$ means that there are $C>0$ and $N$, independent of $p$ and $n$, such that $\mathrm{\mid }{a}_n(p)\mathrm{\mid }\le C{b}_n(p)$ for every $n\in S$ with $n\ge N$ and every $p\in I_n$. The assertion $a_n(p)=o(b_n(p))$ uniformly means that for every $\epsilon >0$ there is an $N$, independent of $p$, such that $\mathrm{\mid }{a}_n(p)\mathrm{\mid }\le \epsilon b_n(p)$ for all those $n$ and $p$. Similarly, events $E_{n,p}$ hold with high probability uniformly over $p\in I_n$ if for every $\epsilon >0$ there is an $N$ such that ${\mathbb{P}}_{n,p}(E_{n,p})\ge 1-\epsilon$ for every $n\in S$ with $n\ge N$ and every $p\in I_n$. Each $E_{n,p}$ is an event in its indicated probability space. Empty parameter sets impose no condition at that index.

For integers $n\ge 1$ and $d\ge 0$, a simple $d$-regular graph on $n$ vertices means a finite graph with no loops or repeated edges in which every vertex has exactly $d$ neighbors. An order is feasible when such a graph exists. Limits over this model are taken through feasible orders; necessarily $0\le d<n$ and $nd$ is even. A fixed-$n$ estimate retains its stated constants and cutoff rather than replacing them by an asymptotic assertion.

The definitions of $o$ and $O$ are, respectively, convergence to zero and eventual boundedness of $a_n\mathrm{/}{b}_n$ in the sequence sense; eventual positivity makes the ratios and inequalities equivalent. Restriction to an unbounded index set simply requires the same inequalities at its indices. These use Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field.

A probability space supplies a probability in $[0,1]$ for each event, so the high-probability definition is an ordinary real-sequence limit. In the finite outcome-weight model, the stated sum formula is the finite probability-space definition. See Probability measures and probability spaces and Finite probability spaces, outcome weights, events, and event probabilities.

The uniform definitions place the cutoff outside the parameter quantifier. Thus a uniform bound applies to any choice $p=p(n)\in I_n$, whereas a result for each fixed $p$ alone need not: for $I_n=(0,1)$, $p^n\to 0$ for each fixed $p$ by For |r| < 1 the sequence rᵏ is null, and for |r| > 1 the sequence |r|ᵏ diverges to +∞, but for $n\ge 1$ with $p_n=1-1\mathrm{/}(2n)$, the factorization $1-p_n^n=(1-p_n){\sum }_{k=0}^{n-1}{p}_n^k\le 1\mathrm{/}2$ gives $p_n^n\ge 1\mathrm{/}2$. The distinction uses the convergence and boundedness notions in Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field.

In a simple $d$-regular graph on $n\ge 1$ vertices, each vertex has at most $n-1$ neighbors. Counting incident vertex-edge pairs by vertices gives $nd$, while counting by edges gives twice the number of edges; hence $nd$ is even. The graph, neighbor and incidence conventions are those of A finite simple graph is a finite vertex set together with a set of two-element vertex subsets and Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree. Feasibility is defined by existence, so these necessary restrictions are not asserted to be sufficient here. The finite-$n$ convention records precisely the constants and cutoff appearing in the relevant quantified inequality.