Janson inequality

There are a couple of inequalities referred to as "Janson inequality" . They provide exponential upper bounds for the probability that a sum of dependent zero-one random variables (cf. also Random variable) equals zero. The underlying probability space corresponds to selecting a random subset of a finite set , where , in such a way that the elements are chosen independently with for each .

Let be a family of subsets of and, for every , let be equal to one if and be zero otherwise. Then counts those elements of which are entirely contained in . Set

Then

(a1)

and, which is better for ,

(a2)

Research leading to these inequalities was motivated by a ground-breaking proof of B. Bollobás [a2], who, in order to estimate the chromatic number of a random graph, used martingales (cf. also Graph colouring; Graph, random; Martingale) to show that the probability of not containing a large clique is very small. Bollobás presented his proof at the opening day of the "Third Conference on Random Graphs (Poznań, July 1987)" . By the end of the meeting S. Janson found a proof of inequality (a1) based on Laplace transforms (cf. also Laplace transform), while T. Łuczak proved a related, less explicit estimate using martingales. The latter result was restricted to a special, though pivotal, context of small subgraphs of random graphs. Soon after, R. Boppana and J. Spencer [a1] gave another proof, resembling the proof of the Lovász local lemma, of the following version of (a1):

(a3)

where . This version puts emphasis on comparison with the independent case.

Under modest symmetry conditions, inequality (a2) appeared in [a3], while the general version was proved in [a4]. See also [a6] for another proof of (a2), but with an extra factor in the exponent.

The quantity is a measure of the pairwise dependence between the s. If , then the exponents in (a1) and (a2) are both equal to , matching asymptotically a lower bound obtained via the FKG inequality, provided further .

Example.

Let be an integer, , and let be the set of all two-element subsets of . With all , , the random subset is a random graph . Let be the family of all triples of pairs of the form , . Then is the number of triangles in , and . Thus, if , then , while for , inequality (a2) yields . As long as , , and the above exponential bounds strengthen the polynomial bound

obtained by the method of second moments, i.e. by a corollary of the Chebyshev inequality. To illustrate the strength of (a1), fix and assume that is divisible by . Then (a1) easily implies that with probability tending to one, more than of the vertices of are covered by vertex-disjoint triangles. Indeed, otherwise there would be a subset of vertices spanning no triangle. By (a1), the probability that this may happen is smaller than

In 1990, Janson [a4] generalized inequality (a2), obtaining an estimate of the lower tail of the distribution of . With , for ,

(a4)

When consists of mutually disjoint sets, is a sum of independent zero-one random variables and (a4) coincides with the (one-sided) Chernoff bound. No corresponding upper tail estimate is true in general.

Also in 1990, W.C.S. Suen [a7] proved a related inequality, which remains valid for a general probability space (and not only for random subsets). In his setting, is a sum of arbitrary indicators , and the bound hinges on the dependency graph induced by them. Suen's inequality has been revived and extended in [a5].

Fore more details on this subject see [a8].

References

[a1]	R. Boppana, J. Spencer, "A useful elementary correlation inequality" J. Combin. Th. A , 50 (1989) pp. 305–307
[a2]	B. Bollobás, "The chromatic number of random graphs" Combinatorica , 8 (1988) pp. 49–56
[a3]	S. Janson, T. Łuczak, A. Ruciński, "An exponential bound for the probability of nonexistence of a specified subgraph in a random graph" M. Karoński (ed.) J. Jaworski (ed.) A. Ruciński (ed.) , Random Graphs '87 , Wiley (1990) pp. 73–87
[a4]	S. Janson, "Poisson approximation for large deviations" Random Struct. Algor. , 1 (1990) pp. 221–230
[a5]	S. Janson, "New versions of Suen's correlation inequality" Random Struct. Algor. , 13 (1998) pp. 467–483
[a6]	J. Spencer, "Threshold functions for extension statements" J. Combin. Th. A , 53 (1990) pp. 286–305
[a7]	W.C.S. Suen, "A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph" Random Struct. Algor. , 1 (1990) pp. 231–242
[a8]	S. Janson, T. Łuczak, A. Ruciński, "Random graphs" , Wiley (2000)