Random graphs and expander graphs can be viewed as sparse
approximations of complete graphs, with Ramanujan expanders
providing the best possible approximations. We formalize this
notion of approximation and ask how well an arbitrary graph can
be...
Read More