====== Alexander Engström (Berkeley) ======

====== Polytopes from Subgraph Statistics ======

===== Abstract for the Combinatorics Seminar 2010 Monday, October 4 =====

Statisticians model large graphs used in the social sciences by counting small subgraphs of different types. For example, let us for every graph on one thousand vertices count the number of triangles and the number of four-cycles. Then plot the dots on an integer grid with the numbers of triangles and four-cycles as the axes. The convex hull of the dots is a polytope whose geometry determines how well one can carry out a maximum likelihood estimate in a corresponding exponential random graph model.

In an ongoing project with Patrik Noren, I study polytopes of this type in larger dimensions. Since many conjectures and theorems by Erdös and coauthors can be restated as facts about particular such polytopes, a complete understanding of the facets is probably unattainable. But we can show that they kind of look like cyclic polytopes containing curvy zonotopes.


----