Limit theorems for monochromatic stars. Issue 4 (16th April 2019) - Bhattacharya, Bhaswar B.; Mukherjee, Sumit
Abstract : Let T ( K 1, r, G n ) be the number of monochromatic copies of the r ‐star K 1, r in a uniformly random coloring of the vertices of the graph G n . In this paper we provide a complete characterization of the limiting distribution of T ( K 1, r, G n ), in the regime where E ( T ( K 1, r, G n ) ) is bounded, for any growing sequence of graphs G n . The asymptotic distribution is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree at most r . Conversely, any limiting distribution of T ( K 1, r, G n ) has a representation of this form. Examples and connections to the birthday problem are discussed.