Universal limit theorems in graph coloring problems with connections to extremal combinatorics. (English) Zbl 1360.05051

Bhattacharya, Bhaswar B.; Diaconis, Persi; Mukherjee, Sumit

Ann. Appl. Probab. 27, No. 1, 337-394 (2017).

Summary: This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs. These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?). It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of colors. This result holds for any graph sequence, deterministic or random. On the other hand, when the number of colors is fixed, a necessary and sufficient condition for asymptotic normality is determined. Finally, using some results from the emerging theory of dense graph limits, the asymptotic (nonnormal) distribution is characterized for any converging sequence of dense graphs. The proofs are based on moment calculations which relate to the results of P. Erdős [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459–464 (1962; Zbl 0116.01202)] and N. Alon [Isr. J. Math. 38, 116–130 (1981; Zbl 0472.05034); ibid. 53, 97–120 (1986; Zbl 0588.05038)] on extremal subgraph counts. As a consequence, a simpler proof of a result of N. Alon [Isr. J. Math. 38, 116–130 (1981; Zbl 0472.05034)], estimating the number of isomorphic copies of a cycle of given length in graphs with a fixed number of edges, is presented.

MSC:

05C15	Coloring of graphs and hypergraphs
60C05	Combinatorial probability
60F05	Central limit and other weak theorems
05D99	Extremal combinatorics

Keywords:

combinatorial probability; extremal combinatorics; graph coloring; limit theorems

Citations:

Zbl 0116.01202; Zbl 0472.05034; Zbl 0588.05038