- 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.