You are here

Generalized birthday problem for April 19

Sumit Mukherjee, Columbia Univ.
Monday, April 19, 2021 - 2:30pm to 3:20pm
Suppose there are \$n\$ students in a class. But assume that not everybody is friends with everyone else, and there is a graph which determines the friendship structure. What is the chance that there are two friends in this class, both with birthdays on April 19? More generally, given a simple labelled graph \$G_n\$ on \$n\$ vertices, color each vertex with one of \$c=c_n\$ colors chosen uniformly at random, independent from other vertices. We study the question: what is the number of monochromatic edges of color 1?

As it turns out, the limiting distribution has three parts, the first and second of which are quadratic and linear functions of a homogeneous Poisson point process, and the third component is an independent Poisson. In fact, we show that any distribution limit must belong to the closure of this class of random variables. As an application, we characterize exactly when the limiting distribution is a Poisson random variable.
This talk is based on joint work with Bhaswar Bhattacharya and Somabha Mukherjee.
Event Type: 
Event Subcalendar: