Limit Theorems for Monochromatic Stars

Bhaswar B. Bhattacharya; Sumit Mukherjee

paper

Limit Theorems for Monochromatic Stars

arXiv:1704.04674

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.

Major changes. Main result extended to general monochromatic stars. Also, the section on monochromatic triangles is removed, as the result appears in more generality in arXiv:1711.01465. 19 pages, 2 figures