When: Sunday, June 6,
10am
Where: Schreiber 309
Speaker: Asaf Cohen Antonir, Tel Aviv University
Title: The Upper Tail Problem for Induced 4-cycles in sparse random
graphs
We initiate the study of the upper tail problem for the random variable counting the number of induced copies of a given graph in the random graph $G_{n,p}$. In particular, building on the techniques from the breakthrough paper of Harel, Mousset, and Samotij, which solved the upper tail problem for cliques, we compute the asymptotics of the upper tail for the number of induced copies of the 4-cycle. We observe a new phenomenon in the theory of large deviations of subgraph counts. This phenomenon is that, in a certain (large) range of $p$, the upper tail of the induced 4-cycle does not admit a naive mean-field approximation.