Probabilistic combinatorics

Probabilistic combinatorics uses probability to prove the existence and typical properties of discrete structures.

An event depending on $n$ holds with high probability when its probability tends to one as $n\to \infty$.

For every fixed $\epsilon >0$, every component of $G(n,(1-\epsilon )/n)$ has $O_{\epsilon }(\log n)$ vertices with high probability. A breadth-first exploration is dominated by a branching process of mean $1-\epsilon$; its total progeny has an exponentially decreasing tail.

A connected graph is unicyclic when it contains exactly one cycle, equivalently when its numbers of vertices and edges agree.

For a decreasing probability sequence $p(n)$, if $G(n,p(n))$ contains a Hamilton cycle with high probability, then $G(n,Cp(n))$ is pancyclic with high probability for every fixed sufficiently large $C$; three independent rounds suffice. One first exposes a Hamiltonian round and uses the independent sprinkled edges to create cycles of every shorter length.

The random alteration method samples a random object and then deletes a small number of offending elements. If few forbidden configurations occur while the desired global property already holds, the altered object witnesses existence.

For bad events with a dependency graph of maximum degree $D$, the symmetric Lovász local lemma guarantees positive probability that none occurs whenever each event has probability at most $p$ and $ep(D+1)\le 1$.

Let $A_1,\dots ,A_m$ be bad events with a lopsidependency graph. If numbers $x_i\in [0,1)$ satisfyfor every $i$, then $\mathbb{P}({\bigcap }_i{A}_i^c)>0$. Unlike the ordinary Lovász local lemma, a lopsidependency graph may omit pairs whose interaction can only make their simultaneous avoidance easier.

Dependent random choice finds a large vertex set whose small subsets have large common neighbourhoods. In a bipartite graph with parts $A,B$, choose random vertices of $B$ with repetition and take their common neighbourhood $X\subseteq A$; convexity gives a lower bound for $\mathbb{E}|X|$, while counting subsets of $X$ with small common neighbourhood allows their deletion.

If a bipartite graph $H$ has $k$ vertices and maximum degree $d$, thenA dependent random choice argument finds, in one colour, enough vertices whose every subset of at most $d$ vertices has a large common neighbourhood; a greedy embedding then places $H$.

If a bipartite graph with parts $A,B$ has density at least $p$, then averaging ordered distinct $t$-tuples gives a common neighbourhood of size at leastIn particular this is at least $p^t|B|/2$ when $|A|$ is sufficiently large compared with $t^2/p$.

The completion form of dependent random choice starts with $t=k-O(\log k)$ vertices having at least $c{2}^{-t}n$ common neighbours in one colour. Reapplying common-neighbourhood sampling inside the remaining polynomial-size set either completes these vertices to a monochromatic $K_{k,k}$ in that colour or produces a $K_{k,k}$ in the other colour. It yields

For disjoint nonempty vertex sets $A,B$, their edge density is

A pair $(A,B)$ is $\epsilon$-regular whenwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$, and $|Y|\ge \epsilon |B|$.

For every $\epsilon >0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partitionwhere $m_0\le m\le M$, $|V_0|\le \epsilon |V|$, the other parts have equal size, and all but at most $\epsilon m^2$ pairs $(V_i,V_j)$ are $\epsilon$-regular.

For every positive density $\alpha$ and positive integer $r$, every sufficiently large subset of $[n]$ of size at least $\alpha n$ contains a nonconstant arithmetic progression of length $r$.

For every $\epsilon >0$ there is $\delta >0$ such that a graph satisfying $e(A,B)\ge p|A||B|$ whenever $|A|,|B|\ge \delta n$, with $p\ge \delta$, has a spanning subgraph $G^{\prime }$ satisfyingfor all disjoint $A,B$. Partition into a fixed large number of nearly equal parts, independently thin each cross-pair to expected density $p$, and apply a concentration inequality and a union bound over all pairs $A,B$.

If a graph $H$ has minimum degree $d$, then its graph Ramsey number satisfies $R(H)\ge 2^{d/2}$. The probabilistic proof chooses a red-blue edge colouring and applies the local lemma to its monochromatic copies of $H$.