Probabilistic combinatorics

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

The semi-random method constructs a combinatorial object in many small random rounds, discarding incompatible proposals and updating the remaining constraints after each round. Independent proposals give calculable expected changes; concentration and deterministic corrections preserve the statistics needed for subsequent rounds. Unlike a single random sample, this combines repeated randomness with a structured evolving state. The Rödl nibble is a matching in a hypergraph version of this method.

For a nearly $D$-regular $s$-uniform hypergraph, sample each edge independently with probability $\alpha /D$, where $\alpha$ is small. Retain the isolated sampled edges as a matching in a hypergraph, and delete every vertex incident to any sampled edge before the next round. A vertex survives with probability $(1-\alpha /D{)}^{d(v)}\approx e^{-\alpha }$; a sampled edge meets another sampled edge with probability at most $s\alpha (1+o(1))$. Thus accepted edges cover order $\alpha$ of the vertices and collision waste is order ${\alpha }^2$. Small hypergraph codegrees control the overlap terms in residual-degree calculations. Repeating a bounded number of rounds while tracking near-regularity is the characteristic Rödl nibble mechanism.

The probabilistic method proves that a combinatorial object exists by defining a random object and showing that the desired property has positive probability. No efficient procedure for finding the object is required.

If a graph has $E$ edges and $T$ triangles, successively delete one edge from a remaining triangle. No new triangle is created and at most $T$ deletions are needed, so a triangle-free subgraph has at least $E-T$ edges. A random-graph expectation lower bound on $E-T$ therefore proves existence of a large triangle-free graph. With edge probability $n^{-1/2}$, the expectation is $(n^2-1)/(3\sqrt{n})$; this is a useful existence bound but is not within a constant factor of the sharp quadratic Mantel theorem bound.

For any fixed density strictly below one, random subsets of an integer interval can have that density yet avoid arithmetic progressions longer than a constant times the logarithm of the interval length. A union bound over possible progressions bounds their occurrence, while concentration of the random cardinality supplies a dense realization. Passing to a subset gives an exact prescribed cardinality.

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.

For fixed $0<\lambda <1$ in $G(n,\lambda /n)$, the largest component of a graph has the displayed order with high probability. A dominating Galton-Watson process gives the tail bound $\mathbb{P}(T\ge j)\le e^{-(\lambda -1-\log \lambda )(j-1)}$ by the exponential Markov inequality. For the lower bound, the tree-component expectation in the Erdős-Rényi model diverges at $j=\lfloor (1-\eta )\log n/(\lambda -1-\log \lambda )\rfloor$. The disjoint-set covariance factor and the exclusion of overlaps give relative variance tending to zero, so the second moment method supplies a tree component of that order.

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

A pseudoforest permits both these components and acyclic tree components.

A labelled unicyclic component has a unique cycle of length $k\ge 3$, with a rooted forest attached to its vertices. Choose its vertices in $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways and its unoriented cycle in $(k-1)!/2$ ways. The labelled forest count with prescribed roots gives $k{n}^{n-k-1}$ attachments. Summing over $k$ and putting $j=n-k$ yields the displayed identity.

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

In an independent random two-colouring of $K_N$, a given $k$-vertex set is monochromatic with probability $2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$. Events on sets intersecting in at most one vertex use disjoint edges. Thus dependency degree is at most $\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(\genfrac{}{}{0ex}{}{N-2}{k-2}\right)$. The Lovász local lemma gives a colouring avoiding all monochromatic $K_k$ when $e{2}^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}(1+(\genfrac{}{}{0ex}{}{k}{2}\left)\right(\genfrac{}{}{0ex}{}{N-2}{k-2}))\le 1$. For $N=ck{2}^{k/2}$ the expression is $O(k^{3/2}(ec/\sqrt{2}{)}^k)$, by Stirling's approximation. Taking $c$ tending sufficiently slowly to $\sqrt{2}/e$ proves $R(k)\ge (\sqrt{2}/e+o(1))k{2}^{k/2}$.

Let $B_v$ be independent Bernoulli random variables on a rooted $d$-ary tree, and put $A_v=\{B_v=1,B_w=0\text{ for every child }w\}$. Events at nonadjacent vertices use disjoint variables, giving a dependency graph of events of maximum degree $d+1$. Assign leaf success probability $p$ and successive probabilities $r_{j+1}=p/(1-r_j{)}^d$. If $p>{\max }_{0\le r\le 1}r(1-r{)}^d=p_d$, the recursion eventually reaches one. Set the final root success probability to one. Each event has probability at most $p$, but following success vertices down from the root must reach an occurring event. Thus the bad events cover the sample space. This gives an upper bound for uniform avoidance thresholds without assuming a converse to the Lovász local lemma.

For countably many constraints on finite-valued variables, each involving finitely many variables, apply the finite Lovász local lemma to every finite constraint subfamily. Partial satisfying assignments on increasing finite variable sets form a finitely branching tree with nonempty levels. The König infinity lemma gives an infinite branch, producing one assignment satisfying all constraints. This existence argument does not assert positive probability of simultaneous avoidance in an infinite product space.

For a finite family with a dependency graph of events, if $0\le x_i<1$ satisfy $\mathbb{P}(E_i)\le x_i{\prod }_{j\in N(i)}(1-x_j)$, then $\mathbb{P}({\bigcap }_i{E}_i^c)\ge {\prod }_i(1-x_i)>0$. Choosing equal $x_i$ gives the familiar symmetric criterion $eq(d+1)\le 1$ when event probabilities are at most $q$ and the maximum dependency degree is $d$.

A dependency graph of events joins potentially dependent events. Each event must be independent of the sigma-algebra generated by all its nonneighbors, a joint condition stronger than pairwise independence. In a product probability space, joining events whose sets of underlying independent variables overlap gives such a graph. This supplies the hypothesis of the Lovász local lemma.

For events $A_i$, a directed graph is an independence digraph if $A_i$ is independent of the sigma-algebra generated by the events indexed by its non-outneighbors, excluding $i$. The direction records which joint independence condition is available. A cyclically oriented triangle imposes pairwise independence; it does not impose independence of all three events together.

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.

For bad events $A_i$, a correlation graph is sufficient for the Lopsided Lovász local lemma when, for every set $S$ of nonneighbors and every positive-probability conditioning event, $\mathbb{P}(A_i\mid {\bigcap }_{j\in S}{A}_j^c)\le \mathbb{P}(A_i)$. A dependency graph of events satisfies this with equality. The condition concerns simultaneous avoidance, not just signs of pairwise correlations.

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.

In a bipartite graph with parts of sizes $m,n$ and density $\delta >0$, a neighbourhood $V^{\prime }$ of size at least $\delta m/2$ can be chosen so that at least a proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ common neighbours. Choose a random vertex on the other side, use the second moment of its degree, and penalize pairs with few common neighbours. This is a simple dependent random choice tool for controlling restricted sumsets.

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

A vertex set $R$ is $(s,k)$-rich when every $s$-element subset of $R$ has at least $k$ common neighbours.

If a bipartite graph $H$ has $k$ vertices and maximum degree at most $d$, then every graph containing a $(d,k)$-rich set of at least $k$ vertices contains a copy of $H$.

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

If a bipartite graph with parts $X,Y$ has at least $\delta |X||Y|$ edges, then the number of ordered tuples $(x_1,x_2,y_1,y_2)\in X^2\times Y^2$ for which every $x_i{y}_j$ is an edge is at leastIndeed, if $d(x_1,x_2)$ is the number of common neighbours of $x_1,x_2$ in $Y$, two applications of the Cauchy-Schwarz inequality give

This is the part-preserving homomorphism density of a four-cycle in a bipartite graph with independently uniform labels $x,x^{\prime }$ in the first part and $y,y^{\prime }$ in the second. Repeated labels are included. It equals the fourth power of the four-cycle norm of the adjacency indicator function. It differs at finite sizes from a count requiring four distinct vertices.

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

The Szemerédi regularity lemma gives equal cells. If every regular cross-cell pair had density at most $1/4$, their total edge contribution would be at most $n^2/8$. Exceptional vertices, within-cell edges and irregular pairs contribute at most $(2\eta +1/(2m_0))n^2$. Choosing $\eta =1/100$ and $m_0=100$ contradicts $e(G)=n^2/6$. The dense pair is $1/8$-regular since it is already $\eta$-regular.

For disjoint nonempty vertex sets $U,V$ of a graph, an $\epsilon$-irregular pair is one that is not an $\epsilon$-regular pair of vertex sets. Equivalently there are witnesses $U^{\prime }\subseteq U$, $V^{\prime }\subseteq V$ with $|U^{\prime }|\ge \epsilon |U|$, $|V^{\prime }|\ge \epsilon |V|$ and $|d(U^{\prime },V^{\prime })-d(U,V)|>\epsilon$. Splitting both cells by these witnesses increases their contribution to the regularity energy by at least ${\epsilon }^4|U||V|/n^2$: the witness rectangle has relative weight at least ${\epsilon }^2$, its mean discrepancy has magnitude greater than $\epsilon$, and the Cauchy-Schwarz inequality bounds the weighted sum of squared discrepancies below by the rectangle weight times its squared mean. This is the local increment in the energy-increment proof of Szemerédi regularity.

For fixed $r$ and positive density threshold $\lambda$, sufficiently regular pairwise dense bipartite graphs between $r$ disjoint equal-sized vertex classes contain at least $\delta n^r$ transversal cliques, for some $\delta >0$. A greedy embedding maintains common neighbourhoods and discards the small set of vertices with atypical degrees into them. The constants depend only on $r,\lambda$.

If three disjoint vertex classes have size $L$, and their three pairs are $\epsilon$-regular pairs of vertex sets of edge density of a bipartite graph at least $d$, where $0<\epsilon \le d/2$ and $\epsilon <1/2$, they contain at least the displayed number of transversal triangles in a graph. All but $2\epsilon L$ vertices in the first class have at least $(d-\epsilon )L$ neighbours in both other classes. Regularity between those two neighbour sets supplies the third edge. This strengthens a mere triangle embedding lemma for regular pairs to a cubic lower count.

Let $X=X_1\bigsqcup \cdots \bigsqcup X_r$ and $Y=Y_1\bigsqcup \cdots \bigsqcup Y_s$ be set partitions of the two parts of a bipartite graph. The pair of partitions is $\epsilon$-regular whenThus a uniformly random pair in $X\times Y$ lies in an irregular cell pair with probability at most $\epsilon$.

For every $\epsilon >0$ there is a positive integer $K(\epsilon )$ such that every finite bipartite graph has an $\epsilon$-regular pair of partitions with at most $K(\epsilon )$ cells on each side.

To prove this, give $X\times Y$ the uniform probability measure, let $f$ be the indicator function of the edge set, and for partitions $\mathcal{P},\mathcal{Q}$ define their energy byThis conditional expectation is an orthogonal projection, so $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$. If the partitions are not $\epsilon$-regular, choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ in every irregular cell pair and refine each $X_i$ by all its $A_{ij}$ and each $Y_j$ by all its $B_{ij}$. The refined energy exceeds the old energy byOn $A_{ij}\times B_{ij}$ the absolute value function of the mean of the difference is greater than $\epsilon$, while this rectangle occupies at least an ${\epsilon }^2$ fraction of $X_i\times Y_j$. The Cauchy-Schwarz inequality therefore contributes more than ${\epsilon }^4|X_i||Y_j|/(|X||Y|)$ from that cell pair. Irregular pairs have total weight greater than $\epsilon$, so every refinement raises the energy by more than ${\epsilon }^5$. The process stops after at most $\lceil {\epsilon }^{-5}\rceil$ refinements. If the current cell counts are $r,s$, the construction gives at most $r{2}^s,s{2}^r$ new cells, so a finite iterated bound depending only on $\epsilon$ supplies $K(\epsilon )$.

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 $\epsilon >0$, all sufficiently large finite graphs admit a set partition into at most $M(\epsilon )$ nonempty cells, each of size at most $\epsilon n$, with the displayed ordered irregular-pair weight bound. Start with small cells. Use regularity energy including diagonal rectangles, refine simultaneously by the witness subsets of all irregular pairs, and apply the refinement variance identity for regularity energy. Each failing round raises energy by more than ${\epsilon }^5$, while energy lies in $[0,1]$. The recurrence $k\mapsto k{2}^k$ bounds the final cell count. Equitability is unnecessary for this weighted version.

A partition with at most $M$ cells has at most $\epsilon n$ vertices in cells smaller than $\epsilon n/M$. Deleting all edges incident to those vertices costs at most $\epsilon n^2$ edges. Every remaining cell has a fixed positive fraction of all vertices, which permits a regular triangle counting lemma to give a cubic count without requiring equal cell sizes.

Use equitable regularity energy with exceptional vertices retained as singleton cells. The refinement variance identity for regularity energy shows that splitting along an irregular pair's witnesses raises energy by more than ${\epsilon }^4|V_i||V_j|/n^2$. More than $\epsilon k^2$ irregular ordered pairs therefore raise energy by more than ${\epsilon }^5/4$ when the exceptional set occupies at most half the vertices.

For equalization with a controlled exceptional set, cut each of the at most $k{2}^k$ witness atoms into pieces of size $\lfloor L/4^k\rfloor$ and put leftovers into singleton exceptional cells. This is a refinement, so it cannot decrease energy. At most $n{2}^{-k}$ vertices are lost. Start with enough cells that this loss, over $\lceil 4{\epsilon }^{-5}\rceil$ rounds, is at most $\epsilon n/2$; the initial exceptional set uses the other half. The number of cells grows by a bounded recurrence depending only on $\epsilon$ and the prescribed minimum. Energy lies in $[0,1]$, so the process terminates.

For fixed forbidden induced patterns, a regularity and Ramsey refinement uses internal clique/independent types and sparse, almost-complete, or intermediate cross pairs. A clique of intermediate pairs realizes every bounded induced pattern consistent with those internal types, using both edge and nonedge regularity. This is the induced embedding consequence used in hereditary graph enumeration theorem; the exceptional-pair budget can be arbitrarily small.

For fixed $r\ge 2$ and every $\epsilon >0$, some $\delta >0$ has the following property for all sufficiently large $n$: a graph with fewer than $\delta n^r$ copies of $K_r$ can be made $K_r$-free by deleting at most $\epsilon n^2$ edges. A Szemerédi regularity lemma partition and the regular clique counting lemma prove this. It converts sparse counts of a forbidden clique into a small edit distance from clique-freeness.

For every $\eta >0$, some $\rho >0$ and $N_0$ have this property: a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ unordered triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. A Szemerédi regularity lemma partition deletes exceptional, intraclass, irregular and sparse-pair edges cheaply. A surviving triangle in a graph would force a positive cubic count by the regular triangle counting lemma.

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

In a proof of the Szemerédi regularity lemma, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell =\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k{2}^k\ell \le kL{2}^{-k}$ vertices are lost. When $L\ge 2\cdot 4^k$, at most $2k{4}^k$ blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded vertices are removed, and every squared edge density of a bipartite graph is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.

If a set partition refines a rectangle $U\times V$ of a graph into rectangles $U_a\times V_b$, write $d=d(U,V)$ for its edge density of a bipartite graph. The weighted variance identity isIt follows by expanding the square and using ${\sum }_{a,b}|U_a||V_b|d(U_a,V_b)=|U||V|d$. In particular, equitable regularity energy cannot decrease under refinement. If a witness rectangle has relative sizes at least $\epsilon$ and edge density of a bipartite graph discrepancy greater than $\epsilon$, its contribution, after division by the squared total vertex count, exceeds ${\epsilon }^4|U||V|/N^2$.

For every finite graph $H$ and density $\delta >0$, sufficiently large vertex classes joined according to $H$ by regular pairs of density at least $\delta$ contain a copy of $H$. The regularity parameter must be sufficiently small in terms of $H$ and $\delta$.

For any fixed odd length $\ell \ge 3$, positive triangle in a graph density forces positive density of $\ell$-cycles. A Szemerédi regularity lemma partition retains a triangle in a graph of regular dense pairs after the sparse and exceptional pairs are removed. Count embeddings of a proper three-colouring of $C_{\ell }$ into those three clusters. The constants depend on $\beta$ and $\ell$, not on graph order.

If the three pairs among vertex sets $A,B,C$ are $\epsilon$-regular and each has density at least $2\epsilon$, where $0<\epsilon <1/2$, then the graph contains a triangle with one vertex in each set.

Given a regularity partition and a density cutoff $\delta$, its reduced graph has one vertex for each nonexceptional class and joins two classes when their pair is regular and has density at least $\delta$.

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 $c>0$, all sufficiently large finite integer sets $A$ with at least $c|A{|}^2$ ordered three-term arithmetic progressions contain a nonconstant four-term arithmetic progression. Cauchy-Schwarz inequality gives $E(A)\ge c^2|A{|}^3$. The Balog-Szemerédi-Gowers theorem supplies a large small-doubling subset. A bounded-modulus Freiman 2-isomorphism gives a positive-density cyclic model; apply the assumed four-term case of Szemerédi's theorem to representatives, then lift the two consecutive second-difference relations.

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