Random Structures & Algorithms

Limit theorems for monochromatic stars

Early View

Let T(K1,r,Gn) be the number of monochromatic copies of the r‐star K1,r in a uniformly random coloring of the vertices of the graph Gn. In this paper we provide a complete characterization of the limiting distribution of T(K1,r,Gn), in the regime where is bounded, for any growing sequence of graphs Gn. 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(K1,r,Gn) has a representation of this form. Examples and connections to the birthday problem are discussed.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.