One often reads that expander graphs look locally like trees. In fact, there are many classes of expander graphs like random regular graphs or some Ramanujan graphs for which it has been shown that they have constant or even logarithmic girth (w.h.p.). Now, girth is not very robust but you might expect that expander graphs contain only few short cycles in general.

Are there results that quantify this concept in terms of the second eigenvalue or edge expansion of the graph? For example, can we remove all cycles of length, say, $k$ by deleting only $f(\lambda_2, k) \cdot n$ edges?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.