Random graphs with near-extreme triangle counts

Speaker(s)

Lorenzo Sadun

Affiliation

University of Texas at Austin

Language of the talk

English

Date

May 22, 2025, 12:15 p.m.

Room

room 4420

Seminar

Seminar of Probability Group

---

We consider large dense random graphs with constraints on the densities $(e,t)$ of edges and triangles. For values of $(e,t)$ near the boundary of the ``Razborov triangle'', we show that all but an exponentially small fraction of such graphs have a block structure with parameters that are analytic functions of $(e,t)$, except at special values where we transition from one phase to another. This follows from an analysis of graphons. Using a new variational principle related to columns of a graphon, we show that the entropy-maximizing graphon is unique and has a ``multipodal'' block structure. This is joint work with Charles Radin.

---