On May 9, 2022, Kyeongsik Nam (남경식) from KAIST gave a talk at the Discrete Math Seminar Kyeongsik Nam (남경식) gave a talk on the number of subgraphs isomorphic to a fixed graph in a random graph and the exponential random graph model at the Discrete Math Seminar. The title of his talk was “Large deviations for subgraph counts in random graphs“.
The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts, called exponential random graph model (ERGM). Despite its importance, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk, I will talk about a brief overview on the upper tail problem and the concentration of measure results for the ERGM. Joint work with Shirshendu Ganguly and Ella Hiesmayr.