Threshold Exponents for Fixed Subgraphs

Why the Densest Part Sets the Scale

In the random graph $G(n,p)$, each possible edge on $n$ vertices is included independently with probability $p$. For a fixed graph $H$, it is natural to ask how large $p$ must be before a copy of $H$ appears. Counting the expected number of copies is a useful starting point, but the vertex-to-edge ratio of all of $H$ need not determine the answer. A denser subgraph of $H$ can be the true obstruction: if that part is absent, then $H$ is absent as well.

Throughout, $H$ is a fixed finite simple graph with at least one edge. A copy of $H$ in a graph is a subgraph isomorphic to $H$; it need not be an induced subgraph, so extra edges among the image vertices are allowed. A subgraph $F$ may use any subset of the vertices and any subset of the edges of $H$ between them. Write $v(F)=|V(F)|$ and $e(F)=|E(F)|$.

Definition: The maximum density of $H$ is $$ m(H)=\max_{\substack{F\subseteq H\\ e(F)>0}}\frac{e(F)}{v(F)}. $$ A subgraph attaining this maximum is called a densest subgraph of $H$. Since $H$ has an edge, $m(H)>0$. The threshold exponent associated with $H$ is $1/m(H)$.

Including all available edges on a chosen vertex set cannot decrease its edge-to-vertex ratio. Thus, when finding $m(H)$, it is enough to consider subgraphs induced by vertex sets, provided they have at least one edge. The definition allows disconnected subgraphs, though a densest subgraph can always be taken to be connected: if a subgraph has multiple components, its ratio is a weighted average of the component ratios, so one component has at least that ratio.

Expected Copies and the Exponent

Let $h=v(H)$ and $e=e(H)$, and let $X_H$ count the distinct copies of $H$ in $G(n,p)$. An injective map from $V(H)$ into the $n$ vertices has probability $p^e$ of sending every edge of $H$ to a present edge. Each copy is counted once for every automorphism of $H$, where an automorphism is an adjacency-preserving bijection from $H$ to itself. If $\operatorname{aut}(H)$ is the number of automorphisms, linearity of expectation gives, for $n\ge h$,

\mathbb{E}X_H=\frac{(n)_h}{\operatorname{aut}(H)}p^e, \qquad (n)_h=n(n-1)\cdots(n-h+1).

For fixed $H$, $(n)_h$ has order $n^h$. If $p=n^{-a}$ for a fixed $a>0$, this expectation has order $n^{h-ae}$. That calculation describes the expected count of $H$, but the threshold is governed by its densest subgraph. To see why, set $p=n^{-1/m(H)}$: for a densest subgraph $F$, the expected number of its copies has order $n^{v(F)}p^{e(F)}=1$, because $e(F)/v(F)=m(H)$. Below this scale that dense subgraph is unlikely to appear; above it, copies of $H$ appear with high probability.

Theorem: Let $H$ be fixed and have at least one edge. If $p=o(n^{-1/m(H)})$, then the probability that $G(n,p)$ contains a copy of $H$ tends to $0$. If $p=\omega(n^{-1/m(H)})$, then that probability tends to $1$. Here $p=o(q)$ means $p/q\to0$, and $p=\omega(q)$ means $p/q\to\infty$, as $n\to\infty$.

Proof. Choose a densest subgraph $F\subseteq H$, with $v=v(F)$, $e_F=e(F)$, and $\operatorname{aut}(F)$ automorphisms. Since $e_F/v=m(H)$, the expected number $X_F$ of copies of $F$ is $\mathbb{E}X_F=(n)_v p^{e_F}/\operatorname{aut}(F)$. If $p=o(n^{-1/m(H)})$, put $w=p n^{1/m(H)}$, so $w\to0$. Then $n^v p^{e_F}=w^{e_F}n^{v-e_F/m(H)}=w^{e_F}\to0$. Since $(n)_v\le n^v$, $\mathbb{E}X_F\to0$. Markov's inequality, $\Pr(X_F\ge1)\le\mathbb{E}X_F$, shows that the probability of a copy of $F$ tends to $0$. Every copy of $H$ contains a copy of $F$, so the probability of a copy of $H$ also tends to $0$.

For the upper range, let $X=X_H$, with $h=v(H)$ and $e=e(H)$. We use the second moment. Fix a copy of $H$ in the counting description of $X$, and compare it with a second copy. If their vertex sets overlap in $k$ vertices and they require $j$ common edges, the number of such ordered pairs is at most $C_H n^{2h-k}$, for a constant $C_H$ depending only on $H$. This holds because there are finitely many ways, depending only on $H$, to identify vertices and edges between two copies. The probability that all required edges in such a pair are present is $p^{2e-j}$. Since $\mathbb{E}X$ has order $n^h p^e$, the contribution of these pairs to $\mathbb{E}[X^2]/(\mathbb{E}X)^2$ is at most a constant times $n^{-k}p^{-j}$.

Pairs with no shared vertices are independent; their normalized contribution tends to $1$, since the proportion of pairs with overlapping vertex sets tends to $0$. For overlapping pairs with $j=0$, we have $k\ge1$, and $n^{-k}p^{-j}=n^{-k}\to0$. For $j\ge1$, their common edges form a subgraph $J\subseteq H$ on at most $k$ vertices. Thus $j/k\le m(H)$. Write $w=p n^{1/m(H)}$, so $w\to\infty$ in this regime. Then $n^{-k}p^{-j}=n^{j/m(H)-k}w^{-j}\le w^{-j}\to0$. There are only finitely many overlap types, so all overlapping contributions together tend to $0$. Therefore $\mathbb{E}[X^2]/(\mathbb{E}X)^2\to1$, and consequently $\operatorname{Var}(X)/(\mathbb{E}X)^2\to0$. Chebyshev's inequality gives $\Pr(X=0)\le\operatorname{Var}(X)/(\mathbb{E}X)^2\to0$. So a copy of $H$ exists with probability tending to $1$. $\square$

Worked Threshold Calculations

Worked Example: A Four-Cycle

Let $H=C_4$, with $V(H)=\{1,2,3,4\}$ and $E(H)=\{12,23,34,41\}$. The full cycle has four edges on four vertices, so its ratio is $4/4=1$. A proper subgraph with edges has at most three edges and at least three vertices if it is a path of length three, giving ratio at most $3/4$; a two-edge path has ratio $2/3$, and a single edge has ratio $1/2$. Hence $m(H)=1$ and the threshold scale is $n^{-1}$.

The cycle has eight automorphisms: four rotations and four reflections. Therefore $\mathbb{E}X_H=(n)_4p^4/8$. At $p=c n^{-1}$, for fixed $c>0$, this is asymptotic to $c^4/8$. At $p=n^{-11/10}$, it is asymptotic to $n^4 n^{-44/10}/8=n^{-2/5}/8$, which tends to $0$. At $p=n^{-9/10}$, it is asymptotic to $n^4n^{-36/10}/8=n^{2/5}/8$, which tends to infinity.

Check: The cycle's density is $1$, so $n^{-1/m(H)}=n^{-1}$. Also, the copy formula divides the $(n)_4$ injective vertex sequences by $8$, exactly the number of ways to list a given four-cycle by choosing a starting vertex and direction.

Worked Example: A Complete Graph on Four Vertices

Let $H=K_4$, with $V(H)=\{1,2,3,4\}$ and $E(H)=\{12,13,14,23,24,34\}$. The complete graph itself has ratio $6/4=3/2$. Any subgraph on three vertices has at most three edges, giving ratio at most $3/3=1$; on two vertices it has at most one edge, giving ratio at most $1/2$. Thus $m(H)=3/2$, and the threshold scale is $n^{-2/3}$.

Each permutation of the four vertices is an automorphism, so $\operatorname{aut}(H)=4\cdot3\cdot2\cdot1=24$. Hence $\mathbb{E}X_H=(n)_4p^6/24$. At $p=c n^{-2/3}$, this is asymptotic to $c^6/24$, since $n^4(n^{-2/3})^6=n^{4-4}=1$. At $p=n^{-3/4}$, it is asymptotic to $n^{4-18/4}/24=n^{-1/2}/24$, which tends to $0$. At $p=n^{-1/2}$, it is asymptotic to $n^{4-3}/24=n/24$, which tends to infinity.

Check: The exponent is $1/(3/2)=2/3$. The six required edges in a copy contribute $p^6$, and dividing the $(n)_4$ injective maps by $24$ counts each set of four vertices once.

Worked Example: A Dense Core with a Long Attachment

Let $H$ have $V(H)=\{1,2,3,4,5,6,7,8\}$ and $E(H)=\{12,13,14,23,24,34,15,56,67,78\}$. Its first four vertices induce a $K_4$; a path of length four is attached at vertex $1$. To verify the maximum density, take any vertex subset and let $k$ be the number of its vertices among $\{1,2,3,4\}$, and $t$ the number among $\{5,6,7,8\}$. The edges it can contain are at most $\binom{k}{2}+t$, because there are at most $\binom{k}{2}$ core edges and at most $t$ edges involving the attached path. For $k=1,2,3$, this bound is at most $k+t$, so its ratio is at most $1$. For $k=4$, the ratio is at most $(6+t)/(4+t)\le3/2$, since $2(6+t)\le3(4+t)$ is equivalent to $t\ge0$. If $k=0$, the selected path vertices have at most $t-1$ edges when $t\ge1$. Thus no subgraph is denser than the core, and $m(H)=6/4=3/2$. The threshold scale is $n^{-2/3}$.

The only vertices that can be permuted by an automorphism are $2,3,4$: vertex $1$ is the unique core vertex incident to the attached path, and the path's successive vertices are distinguished by their distances from $1$. All six permutations of $2,3,4$ are allowed, so $\operatorname{aut}(H)=6$. Therefore $\mathbb{E}X_H=(n)_8p^{10}/6$. At $p=n^{-7/10}$, this expectation is asymptotic to $n^8 n^{-7}/6=n/6$, which diverges. Yet $p/n^{-2/3}=n^{-7/10+2/3}=n^{-1/30}\to0$, so this probability is below the threshold scale. Indeed, the expected number of $K_4$ copies is asymptotic to $n^4(n^{-7/10})^6/24=n^{4-21/5}/24=n^{-1/5}/24$, which tends to $0$. Since every copy of $H$ contains a $K_4$, the probability of a copy of $H$ tends to $0$, despite its expected copy count tending to infinity.

Check: The edge count of $H$ is $6+4=10$, so the copy expectation uses $p^{10}$. The dense core has six edges on four vertices and sets the exponent $2/3$; the attached path lowers the average density of the whole graph to $10/8=5/4$, which explains why the expectation of $H$ alone can be misleading.

Reading the Expectation Regimes Correctly

For $p=c n^{-1/m(H)}$, with fixed $c>0$, a densest subgraph $F$ with $v(F)$ vertices and $e(F)$ edges has expected copy count asymptotic to $c^{e(F)}/\operatorname{aut}(F)$. This is the scale at which that obstruction has an order-one expectation. The later study of Poisson limits concerns more precise behavior in a special case; an order-one expectation by itself does not establish a limiting distribution.

Above the threshold, the proof shows more than a diverging expectation: it establishes that a copy exists with probability tending to $1$. Below the threshold, the expectation of copies of a densest subgraph tends to $0$, which rules out $H$. But the expectation of copies of $H$ itself need not tend to $0$, as the attached-path example shows. In that example, the rare graphs containing the $K_4$ core can contribute many attached-path copies, making the mean large even though the probability of seeing the core tends to zero.

Common pitfall. A tempting but incorrect calculation is to set the threshold by solving $n^{v(H)}p^{e(H)}\approx1$, yielding $p\approx n^{-v(H)/e(H)}$. That uses only the average density of all of $H$. For the attached-path graph, it gives $n^{-8/10}=n^{-4/5}$, whereas the $K_4$ core gives the actual exponent $n^{-2/3}$. The correction is to maximize $e(F)/v(F)$ over subgraphs first, then take its reciprocal. A dense part cannot be bypassed: any copy of the whole graph must contain a copy of that part.

Check Your Understanding

Use the maximum-density definition and distinguish expected counts from existence probabilities.

For $H=K_3$, compute $m(H)$ and the threshold exponent.
Suppose a fixed graph $H$ has a subgraph with five edges on four vertices, and no subgraph has larger density. What is $m(H)$, and what is the threshold scale?
Explain why a diverging expectation for the number of copies of $H$ does not, by itself, prove that $H$ appears with high probability.
In the theorem's lower regime, why is it enough to count copies of a densest subgraph rather than copies of all of $H$?
In the upper-regime proof, why does an overlap with $j\ge1$ common edges have $j/k\le m(H)$?

Threshold Exponents for Fixed Subgraphs

What You'll Learn