Universal Limit Theorems in Graph Coloring Problems With Connections to Extremal Combinatorics

Understand

This paper proves limit theorems for the number of monochromatic edges in uniform random colorings of general random graphs.

• These can be seen as generalizations of the birthday problem (what is the chance that there are two friends with the same birthday?).
• It is shown that if the number of colors grows to infinity, the asymptotic distribution is either a Poisson mixture or a Normal depending solely on the limiting behavior of the ratio of the number of edges in the graph and the number of colors.
• This result holds for any graph sequence, deterministic or random.