Measure when a random structure appears

Try

In the random graph G(n, p), each possible edge of a finite simple graph on n labeled vertices is present independently with probability p. The parameter describes the construction, not a claim that an observed real network has independent edges. We will ask when a triangle appears and prove probability bounds, separating a suggestive expected count from a genuine high-probability conclusion.

Predict

Predict why a large expectation alone may fail to show existence with high probability. A random variable can be zero most of the time and enormous on rare outcomes. To rule out that concentration pattern, control a second moment or variance. For triangle counts, dependence is localized: triangles with disjoint edge sets have independent indicators, while triangles sharing one edge have positive covariance.

Experiment

Classify pairs of distinct triangles.

Shared vertices	Shared edges	Joint occurrence probability	Covariance
0 or 1	0	p^6	0
2	1	p^5	p^5−p^6

The three-shared-vertex case is the same triangle and belongs in the individual variance term. A common vertex alone does not create dependence because the defining edge sets are still disjoint.

Understand

Let X be the number of triangles and N=C(n, 3). Each indicator has mean p³ and variance p³(1−p³), so E[X]=Np³. There are C(n, 2)C(n−2, 2) unordered pairs of triangles sharing an edge: choose the common edge and then their two distinct third vertices. Consequently Var (X)=Np³(1−p³)+2C(n, 2)C(n−2, 2)(p^5−p^6). The factor two comes from expanding the variance of a sum over unordered pairs. For n=4, p=1/2 this gives 5/8, while the mean is 1/2, showing why the variance need not equal the mean.

Apply

If np tends to zero as n grows, E[X]≤(np)³/6 tends to zero and Markov gives P(X≥1)→0. If np tends to infinity, the variance divided by the squared mean is bounded by a constant times 1/(n³p³)+1/(n²p), which tends to zero. Chebyshev then gives P(X=0)≤Var (X)/(E[X])²→0. Thus p of order 1/n is the threshold scale for the appearance of a triangle. These two regimes do not describe the precise limiting probability when np approaches a fixed positive constant; that needs a finer distributional analysis.

The second-moment inequality can also be written P(X>0)≥E[X]²/E[X²] for a nonnegative random variable with finite second moment. Apply Cauchy–Schwarz to X times the indicator of X>0. Since E[X²]=Var (X)+E[X]², a vanishing relative variance makes this lower bound approach one. This derivation explains why controlling the second moment supplies information that a first moment alone cannot.

Continue

For isolated vertices, the expectation is n(1−p)^(n−1), because all n−1 incident edges must be absent. That expression suggests a different scale near log (n)/n, but it does not alone prove the full connectivity threshold. Other disconnected components must also be controlled. This is a useful discipline for random-model claims: name the event actually bounded, state the asymptotic assumptions, and avoid upgrading a first-moment calculation into a theorem about a broader graph property. Simulations can illustrate the transition but do not replace the probability proof.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Use a fresh graph and an independently chosen counting problem to test transfer before writing a synthesis report.