Large Structures Seminar: Alexander Engström

The set of graphs can be compactified by adding random graph models as new points. This theory of “graph limits” or “graphons” has been developed during the last years by Lovasz and coauthors. Some parts of the theory also follow from older very general considerations in probability theory by Aldous and Hoover. It’s not easy to tell if two graphs are isomorphic and for graph limits this is a similar but even harder measure theoretic problem. In joint work with Patrik Noren we propose a theory of algebraic graph limits which cuts out a dense subset of graph limits. For these algebraic graph limits we conjecture that the isomorphsim problem is easy to solve, and we prove special cases of this. The algebraic graph limits also provide a natural filtration on random graph models starting of with Erdös-Renyi, preferential attachment, and other models that are commonly considered in applications, and varieties defined by subgraph statistics define natural model tests.