Comparison of Metric Spectral Gaps

Assaf Naor

Analysis and Geometry in Metric Spaces, Tome 2 (2014), / Harvested from The Polish Digital Mathematics Library

Résumé

Let A = (aij) ∊ Mn(ℝ) be an n by n symmetric stochastic matrix. For p ∊ [1, ∞) and a metric space (X, dX), let γ(A, dpx) be the infimum over those γ ∊ (0,∞] for which every x1, . . . , xn ∊ X satisfy [...] Thus γ (A, dpx) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel dpX : X × X →[0,∞). We study pairs of metric spaces (X, dX) and (Y, dY ) for which there exists Ψ: (0,∞)→(0,∞) such that γ (A, dpX) ≤Ψ (A, dpY ) for every symmetric stochastic A ∊ Mn(ℝ) with (A, dpY ) < ∞. When Ψ is linear a complete geometric characterization is obtained. Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if n ∊ ℕ and p ∊ (2,∞) then for every f1, . . . , fn ∊ Lp there exist x1, . . . , xn ∊ L2 such that [...] and [...] This statement is impossible for p ∊ [1, 2), and the asymptotic dependence on p in (0.1) is sharp. We also obtain the best known lower bound on the Lp distortion of Ramanujan graphs, improving over the work of Matoušek. Links to Bourgain-Milman-Wolfson type and a conjectural nonlinear Maurey-Pisier theorem are studied.

Détail

Publié le : 2014-01-01

Zbl 1316.46023

EUDML-ID : urn:eudml:doc:266745

Bibliographie

[1] N. Alon, R. Boppana, and J. Spencer. An asymptotic isoperimetric inequality. Geom. Funct. Anal., 8(3), 411-436, 1998.[Crossref] | Zbl 0907.60018

[2] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2), 271-284, 1994. | Zbl 0798.05048

[3] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1), 1-21 (electronic), 2008. | Zbl 1132.68070

[4] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2), Art. 5, 37, 2009. | Zbl 1325.68255

[5] P. Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4), 429-448, 1983. | Zbl 0597.54015

[6] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2), 137-172, 1992.[Crossref] | Zbl 0788.46050

[7] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3), 463-482, 1994. | Zbl 0803.47037

[8] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. ofMath. (2), 162(2), 643-709, 2005. | Zbl 1114.46007

[9] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000. | Zbl 0946.46002

[10] P. Biswal, J. R. Lee, and S. Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM, 57(3), Art. 13, 23, 2010. | Zbl 1327.05199

[11] B. Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2(2), 125-134, 1982.[Crossref] | Zbl 0505.05053

[12] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2), 46-52, 1985. | Zbl 0657.46013

[13] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1), 295-317, 1986. | Zbl 0617.46024

[14] M. R. Bridson and A. Haefliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999.

[15] A. Z. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 286-294, 1987.

[16] A.-P. Calderón. Intermediate spaces and interpolation, the complex method. Studia Math., 24, 113-190, 1964. | Zbl 0204.13703

[17] F. Chaatit. On uniform homeomorphisms of the unit spheres of certain Banach lattices. Pacific J.Math., 168(1), 11-31, 1995. | Zbl 0823.46016

[18] I. Chavel. Eigenvalues in Riemannian geometry, volume 115 of Pure and Applied Mathematics. Academic Press Inc., Orlando, FL, 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk.

[19] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2), Art. 22, 18, 2008. | Zbl 1297.68234

[20] J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pages 195-199. Princeton Univ. Press, Princeton, N. J., 1970.

[21] D. Christofides and K. Markström. Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Structures Algorithms, 32(1), 88-100, 2008. | Zbl 1130.05030

[22] F. Chung. Diameters and eigenvalues. J. Amer. Math. Soc., 2(2), 187-195, 1989.[Crossref] | Zbl 0678.05037

[23] M. Cwikel and S. Reisner. Interpolation of uniformly convex Banach spaces. Proc. Amer. Math. Soc., 84(4), 555-559, 1982.[Crossref] | Zbl 0497.46052

[24] M. de la Salle. Towards Banach space strong property (T) for SL(3, R). Preprint available at http://arxiv.org/abs/1307.2475, 2013.

[25] N. R. Devanur, S. A. Khot, R. Saket, and N. K. Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 537-546. ACM, New York, 2006. | Zbl 1301.05332

[26] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

[27] J. Ding, J. R. Lee, and Y. Peres. Markov type and threshold embeddings. Geom. Funct. Anal., 23(4), 1207-1229, 2013.[Crossref] | Zbl 1279.46013

[28] J. Elton. Sign-embeddings of ln1 . Trans. Amer. Math. Soc., 279(1), 113-124, 1983. | Zbl 0525.46011

[29] P. Enflo. Uniform homeomorphisms between Banach spaces. In Séminaire Maurey-Schwartz (1975-1976), Espaces, Lp, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, page 7. CentreMath., École Polytech., Palaiseau, 1976. | Zbl 0341.46009

[30] J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Approximation, randomization, and combinatorial optimization, volume2764 of Lecture Notes in Comput. Sci., pages 36-46. Springer, Berlin, 2003. | Zbl 1279.05053

[31] U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures Algorithms, 20(3), 403-440, 2002. Probabilistic methods in combinatorial optimization. [32] M. Fiedler. Laplacian of graphs and algebraic connectivity. In Combinatorics and graph theory (Warsaw, 1987), volume 25 of Banach Center Publ., pages 57-70. PWN, Warsaw, 1989. | Zbl 1005.90052

[33] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56, 121-155, 1976. | Zbl 0344.46052

[34] T. Figiel, W. B. Johnson, and G. Schechtman. Random sign embeddings from lnr , 2 < r < 1. Proc. Amer. Math. Soc., 102(1), 102-106, 1988. | Zbl 0655.46016

[35] J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., 195(910), viii+100, 2008. | Zbl 1177.05070

[36] E. D. Gluskin, A. Pietsch, and J. Puhl. A generalization of Khintchine’s inequality and its application in the theory of operator ideals. Studia Math., 67(2), 149-155, 1980. | Zbl 0441.47032

[37] F. Göring, C. Helmberg, and S. Reiss. Graph realizations associated with minimizing themaximumeigenvalue of the Laplacian. Math. Program., 131(1-2, Ser. A), 95-111, 2012. | Zbl 1232.05124

[38] F. Göring, C. Helmberg, and M. Wappler. Embedded in the shadow of the separator. SIAM J. Optim., 19(1), 472-501, 2008. | Zbl 1169.05347

[39] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1), 73-146, 2003.[Crossref] | Zbl 1122.20021

[40] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993. | Zbl 0837.05001

[41] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, pages 534-543, 2003.

[42] L. H. Harper. Optimal numberings and isoperimetric problems on graphs. J. Combinatorial Theory, 1, 385-393, 1966. | Zbl 0158.20802

[43] I. Haviv and O. Regev. The Euclidean distortion of flat tori. J. Topol. Anal., 5(2), 205-223, 2013. | Zbl 1279.46014

[44] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.[Crossref] | Zbl 0985.46008

[45] T. Hytönen and A. Naor. Pisier’s inequality revisited. Studia Math., 215(3), 221-235, 2013. | Zbl 1285.46007

[46] M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for markov chains: the approximation of the permanent resolved (preliminary version). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 235-244, 1988.

[47] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitzmappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189-206. Amer. Math. Soc., Providence, RI, 1984.

[48] D. M. Kane and R. Meka. A PRG for Lipschitz functions of polynomials with applications to sparsest cut. In STOC’13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 1-10, 2013. | Zbl 1293.65007

[49] G. Kasparov and G. Yu. The coarse geometric Novikov conjecture and uniform convexity. Adv. Math., 206(1), 1-56, 2006.[Crossref] | Zbl 1102.19003

[50] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4), 821-852, 2006. | Zbl 1102.46051

[51] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fundam. Math., 22, 77-108, 1934. | Zbl 0009.03904

[52] P. N. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 682-690, 1993. | Zbl 1310.90017

[53] T. Kondo. CAT(0) spaces and expanders. Mathematische Zeitschrift, pages 1-13, 2011.

[54] R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L1. SIAM J. Comput., 38(6), 2487-2498, 2009. | Zbl 1191.68869

[55] E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Eficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2), 457-474 (electronic), 2000. | Zbl 0963.68078

[56] V. Lafiorgue. Un renforcement de la propriété (T). Duke Math. J., 143(3), 559-602, 2008.

[57] V. Lafiorgue. Propriété (T) renforcée Banachique et transformation de Fourier rapide. J. Topol. Anal., 1(3), 191-206, 2009.

[58] U. Lang and T. Schlichenmaier. Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Int.Math. Res. Not., 58, 3625-3655, 2005.[Crossref] | Zbl 1095.53033

[59] G. F. Lawler and A. D. Sokal. Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality. Trans. Amer. Math. Soc., 309(2), 557-580, 1988. | Zbl 0716.60073

[60] M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.

[61] J. R. Lee. On distance scales, embeddings, and eficient relaxations of the cut cone. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92-101 (electronic), New York, 2005. ACM. | Zbl 1297.68244

[62] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1), 59-95, 2005. | Zbl 1074.46004

[63] J. R. Lee and A. Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193-201, 2010. | Zbl 1288.05062

[64] B. Liao. Strong Banach property (T) for simple algebraic groups of higher rank. Preprint available at http://arxiv.org/abs/ 1301.1861, 2013.

[65] J. Lindenstrauss. On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J., 10, 241-252, 1963. | Zbl 0115.10001

[66] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2), 215-245, 1995.[Crossref] | Zbl 0827.05021

[67] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3), 261-277, 1988.[Crossref] | Zbl 0661.05035

[68] R. Lyons and Y. Peres. Probability on Trees and Networks. Forthcoming book, available at http://mypage.iu.edu/~rdlyons/ prbtree/book.pdf, 2013. [69] G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1), 51-60, 1988.

[70] J. Matoušek. On embedding expanders into `p spaces. Israel J. Math., 102, 189-197, 1997. | Zbl 0947.46007

[71] B.Maurey. Type, cotype and K-convexity. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1299-1332. North- Holland, Amsterdam, 2003.

[72] B.Maurey and G. Pisier. Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math., 58(1), 45-90, 1976. | Zbl 0344.47014

[73] S. Mazur. Une remarque sur l’homéomorphie des champs fonctionels. Studia Math., 1, 83-85, 1929. | Zbl 55.0242.01

[74] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247-298, 2008. Preliminary version in SODA ’06. | Zbl 1187.46014

[75] M. Mendel and A. Naor. Nonlinear spectral calculus and super-expanders. To appear in Inst. Hautes Études Sci. Publ. Math., available at http://arxiv.org/abs/1207.4705, 2012.

[76] M. Mendel and A. Naor. Expanders with respect to Hadamard spaces and random graphs. Preprint available at http://arxiv.org/abs/1306.5434, 2013. | Zbl 1316.05109

[77] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1, 163-199, 2013. | Zbl 1297.54037

[78] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2), 167-233, 2012. | Zbl 1261.46013

[79] A. Naor. On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs. Comb. Probab. Comput., 21(4), 623-634, 2012.[Crossref] | Zbl 1247.05104

[80] A. Naor, Y. Peres, O. Schramm, and S. Shefield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J., 134(1), 165-197, 2006. | Zbl 1108.46012

[81] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal., 227(2), 273-303, 2005. | Zbl 1104.68087

[82] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552, 213-236, 2002. | Zbl 1033.46013

[83] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Compos. Math., 147(5), 1546-1572, 2011. | Zbl 1267.20057

[84] I. Newman and Y. Rabinovich. Hard metrics from Cayley graphs of abelian groups. Theory Comput., 5, 125-134, 2009. | Zbl 1213.05126

[85] E. Odell and T. Schlumprecht. The distortion problem. Acta Math., 173(2), 259-281, 1994. | Zbl 0828.46005

[86] S.-i. Ohta. Extending Lipschitz and Hölder maps between metric spaces. Positivity, 13(2), 407-425, 2009.[Crossref] | Zbl 1198.54048

[87] S.-i. Ohta. Markov type of Alexandrov spaces of non-negative curvature. Mathematika, 55(1-2), 177-189, 2009.[Crossref] | Zbl 1195.46019

[88] N. Ozawa. A note on non-amenability of B(lp) for p = 1, 2. Internat. J. Math., 15(6), 557-565, 2004.

[89] G. Pisier. Sur les espaces de Banach qui ne contiennent pas uniformément de l1 n. C. R. Acad. Sci. Paris Sér. A-B, 277, A991-A994, 1973. | Zbl 0271.46011

[90] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4), 326-350, 1975. | Zbl 0344.46030

[91] G. Pisier. La méthode d’interpolation complexe: applications aux treillis de Banach. In Séminaire d’Analyse Fonctionnelle (1978-1979), pages Exp. No. 17, 18. École Polytech., Palaiseau, 1979. | Zbl 0412.46026

[92] G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167-241. Springer, Berlin, 1986.

[93] G. Pisier. Complex interpolation between Hilbert, Banach and operator spaces. Mem. Amer. Math. Soc., 208(978), vi+78, 2010. | Zbl 1213.46002

[94] Y. Rabinovich. On average distortion of embedding metrics into the line. Discrete Comput. Geom., 39(4), 720-733, 2008.[Crossref] | Zbl 1158.68050

[95] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 300-306 (electronic), New York, 1999. ACM.

[96] Y. Raynaud. On ultrapowers of non commutative Lp spaces. J. Operator Theory, 48(1), 41-68, 2002. | Zbl 1029.46102

[97] C. A. Rogers. A note on coverings and packings. J. London Math. Soc., 25, 327-331, 1950. | Zbl 0038.02902

[98] J. Sun, S. Boyd, L. Xiao, and P. Diaconis. The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev., 48(4), 681-699, 2006.[Crossref] | Zbl 1109.60324

[99] M. Talagrand. An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities. Proc. Amer.Math. Soc., 104(3), 905-909, 1988.[Crossref] | Zbl 0691.60015

[100] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991