Premium
Limit theorems for monochromatic stars
Author(s) -
Bhattacharya Bhaswar B.,
Mukherjee Sumit
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20856
Subject(s) - mathematics , combinatorics , bounded function , monochromatic color , limit (mathematics) , limiting , discrete mathematics , random graph , graph , sequence (biology) , star (game theory) , asymptotic distribution , random variable , poisson distribution , distribution (mathematics) , physics , mathematical analysis , mechanical engineering , statistics , estimator , biology , optics , genetics , engineering
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.