What is the chance that among a group of n friends, there are s friends all of whom have the same birthday? This is the celebrated birthday problem which can be formulated as the existence of a monochromatic s-clique (s matching birthdays) in the complete graph Kn, where every vertex of Kn is uniformly colored with 365 colors (corresponding to birthdays). More generally, for a connected graph H, let T(H, Gn) be the number of monochromatic copies of H in a uniformly random coloring of the vertices of the graph Gn with cn colors. In this talk, the asymptotics of this quantity will be derived in the various regimes, and applications in distributional property testing, computation of discrete logarithms, and network inference, will be discussed.