Nonlinear spectral calculus and super-expanders

Manor Mendel, Assaf Naor

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


Nonlinear spectral gaps with respect to uniformly convex normed spaces are shown to satisfy a spectral calculus inequality that establishes their decay along Cesàro averages. Nonlinear spectral gaps of graphs are also shown to behave sub-multiplicatively under zigzag products. These results yield a combinatorial construction of super-expanders, i.e., a sequence of 3-regular graphs that does not admit a coarse embedding into any uniformly convex normed space.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)1-95
عدد الصفحات95
دوريةPublications Mathematiques de l'Institut des Hautes Etudes Scientifiques
مستوى الصوت119
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - مايو 2014

ملاحظة ببليوغرافية

Funding Information:
Michael Langberg was involved in early discussions on the analysis of the zigzag product. Keith Ball helped in simplifying this analysis. We thank Steven Heilman, Michel Ledoux, Mikhail Ostrovskii and Gideon Schechtman for helpful suggestions. We are also grateful to two anonymous referees for their careful reading of this paper and many helpful comments. An extended abstract announcing parts of this work, and titled “Towards a calculus for nonlinear spectral gaps”, appeared in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). M. M. was partially supported by ISF grants 221/07 and 93/11, BSF grants 2006009 and 2010021, and a gift from Cisco Research Center. Part of this work was completed while M.M. was a member of the Institute for Advanced Study at Princeton, NJ, USA. A.N. was partially supported by NSF grant CCF-0832795, BSF grants 2006009 and 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A.N. was visiting Université Pierre et Marie Curie, Paris, France.


أدرس بدقة موضوعات البحث “Nonlinear spectral calculus and super-expanders'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا