Graph Limits and Their Uniqueness

Theory of graph limits aims to provide analytic models representing large graphs. Such models have found applications in various areas of computer science, mathematics (extremal combinatorics in particular) and network science. In this talk, we will focus on large dense graphs and their limits. Motivated by problems from extremal graph theory, Lovasz and Szegedy initiated a systematic study of graph limits that are uniquely determined by finitely many density constraints, so-called finitely forcible graphons, and conjectured that all such graphons must have a simple structure. On the contrary, we will show that finitely forcible graphons can contain any computable graphon as a subgraphon. Our result provides a unified framework for constructing complex finitely forcible graphons, which includes many earlier ad hoc constructions of finitely forcible graphons.

The talk is based on joint work with Jacob Cooper and Taisa Martins. The talk will be self-contained and no previous knowledge of graph limits will be assumed.