A random graph model for approximating sparse graphs

Series: 
ACO Student Seminar
Friday, April 21, 2017 - 13:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
School of Mathematics, Georgia Tech
Organizer: 
Beginning with Szemerédi’s regularity lemma, the theory of graph decomposition and graph limits has greatly increased our understanding of large dense graphs and provided a framework for graph approximation. Unfortunately, much of this work does not meaningfully extend to non-dense graphs. We present preliminary work towards our goal of creating tools for approximating graphs of intermediate degree (average degree o(n) and not bounded). We give a new random graph model that produces a graph of desired size and density that approximates the number of small closed walks of a given sparse graph (i.e., small moments of its eigenspectrum). We show how our model can be applied to approximate the hypercube graph. This is joint work with Santosh Vempala.