Random graphs with near-extreme triangle counts

Prelegent(ci)

Lorenzo Sadun

Afiliacja

University of Texas at Austin

Język referatu

angielski

Termin

22 maja 2025 12:15

Pokój

p. 4420

Seminarium

Seminarium Zakładu Rachunku Prawdopodobieństwa

---

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.

---