Corelab Seminar

Paris Syminelakis
Symmetric Graph Properties Have Independent Edges

In the study of random structures we often face a trade-off between realism and tractability, the latter typically enabled by independence assumptions. In this work we initiate an e ffort to bridge this gap by developing tools that allow us to work with independence without assuming it. Let G_n be the set of all graphs on n vertices and let S be an arbitrary subset of G_n, e.g., the set of all graphs with m edges. The study of random networks can be seen as the study of properties that are true for most elements of S, i.e., that are true with high probability for a uniformly random element of S. With this in mind, we pursue the following question: "what are general sufficient conditions for the uniform measure on a set of graphs S \subset G_n to be well-approximable by a product measure on the set of all possible edges?"

This is joint work with Dimitris Achlioptas (UC Santa Cruz) and appeared in ICALP'2015.