Limit theorems for monochromatic stars. Issue 4 (16th April 2019)

• Record Type: Journal Article
• Authors: Bhattacharya, Bhaswar B.; Mukherjee, Sumit
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 831
• Page End: 853
• Publication Date: 2019-04-16
• Subjects: combinatorial probability -- graph coloring -- limit theorems -- subgraph counts; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20856
• Languages: English
• ISSNs: 1042-9832

Abstract

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.