A random graph model for approximating sparse graphs

Series
ACO Student Seminar
Time
Friday, April 21, 2017 - 1:05pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Samantha Petti – School of Mathematics, Georgia Tech
Organizer
Marcel Celaya
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.