Limit Theorems for Monochromatic 2-Stars and Triangles

Bhaswar B. Bhattacharya, Sumit Mukherjee

Published 2017-04-15Version 1

In this paper we study the asymptotic limiting distribution of the number of monochromatic 2-stars and triangles in a growing sequence of graphs where the vertices are colored independently and uniformly at random. We show that the asymptotic distribution of the number of monochromatic 2-stars for any graph sequence is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree 1 or 2. Moreover, any limiting distribution for the number of monochromatic 2-stars has a representation of this form. The number of monochromatic triangles is more challenging to characterize; in this case, the limiting distributions can involve products and mixtures of Poisson random variables. We derive conditions under which the number of monochromatic triangles is asymptotically Poisson. As a consequence, an interesting second-moment phenomenon emerges: the number of monochromatic 2-stars or triangles converges to a Poisson distribution whenever the limits of their corresponding mean and the variance are equal.