Janson inequalities and subgraph counts

Let R be a random subset of a finite ground set, each element included independently with its own fixed probability. For each fixed support S_i, let A_i mean that all elements of S_i belong to R. Count occurrences with X equal to the sum of their indicators and denote its mean by mu. In a graph application the ground elements are possible edges, not vertices, unless the random experiment actually samples vertices. Each support is the edge set of a particular pattern copy.

Join two distinct supports when they intersect and define Delta by summing their joint probabilities over ordered distinct intersecting pairs. Thus a dependent unordered pair contributes twice. The summand is the probability that the whole union of the supports is present, not their covariance and not the product of their marginal probabilities. Diagonal terms are excluded from Delta. Some references use an unordered convention or include diagonal terms, changing formulas; fix the definition before importing a theorem’s constants.

Two triangles that share one vertex have disjoint edge supports, so their occurrence indicators are independent in G(n,p). Two triangles sharing an edge have a five-edge union and joint probability p to the fifth power. On four vertices there are four triangles and six unordered pairs of distinct triangles; every pair shares one edge. Consequently Delta has twelve, not six, equal joint-probability terms. This elementary case is an effective way to catch a missing factor of two.

When Delta is much smaller than mu, the absence bound resembles an independent rare-event exponential. When overlap is large, the first bound can become uninformative even though the count is usually positive. One useful lower-tail form incorporates both the diagonal scale mu and the overlap scale Delta in its denominator. Assuming mu>0, it applies to deviations t between zero and mu, including t=mu for absence. If mu=0 then nonnegativity forces X=0 almost surely, which is handled separately without a denominator formula. The denominator is not simply the variance, and no claim is made that Delta equals the entire dependence structure.

The absence upper bound need not be close to the actual absence probability at finite size. In particular, treating overlapping pattern indicators as independent produces a different number, often with no justified inequality direction unless a correlation theorem is also invoked. An exact enumeration for a tiny graph can audit the calculation without being a proof for larger graphs. For asymptotic use, one must count every relevant intersection type and compare its contribution on the same scale as the squared mean or the intended exponential rate.

Containment is also a real restriction. An induced-copy event requires some edges present and other edges absent, so it is not directly a positive containment event on the original edge ground set. Arbitrary color-pattern events or martingale differences likewise do not automatically satisfy this setup. A more general theorem may apply, but its assumptions must be checked separately. Here both examples use only fixed triangles requiring their edges, with no absence constraints, making the product-space interpretation exact.