PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 2 | 1 |
Tytuł artykułu

Comparison of Metric Spectral Gaps

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
2
Numer
1
Opis fizyczny
Daty
wydano
2014-01-01
otrzymano
2013-08-19
zaakceptowano
2013-12-23
online
2014-02-28
Twórcy
autor
Bibliografia
  • [1] N. Alon, R. Boppana, and J. Spencer. An asymptotic isoperimetric inequality. Geom. Funct. Anal., 8(3), 411-436, 1998.[Crossref]
  • [2] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2), 271-284, 1994.
  • [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.
  • [4] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2), Art. 5, 37, 2009.
  • [5] P. Assouad. Plongements lipschitziens dans Rn. Bull. Soc. Math. France, 111(4), 429-448, 1983.
  • [6] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2), 137-172, 1992.[Crossref]
  • [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.
  • [8] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. ofMath. (2), 162(2), 643-709, 2005.
  • [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.
  • [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.
  • [11] B. Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2(2), 125-134, 1982.[Crossref]
  • [12] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2), 46-52, 1985.
  • [13] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1), 295-317, 1986.
  • [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.
  • [17] F. Chaatit. On uniform homeomorphisms of the unit spheres of certain Banach lattices. Pacific J.Math., 168(1), 11-31, 1995.
  • [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.
  • [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.
  • [22] F. Chung. Diameters and eigenvalues. J. Amer. Math. Soc., 2(2), 187-195, 1989.[Crossref]
  • [23] M. Cwikel and S. Reisner. Interpolation of uniformly convex Banach spaces. Proc. Amer. Math. Soc., 84(4), 555-559, 1982.[Crossref]
  • [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.
  • [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]
  • [28] J. Elton. Sign-embeddings of ln1 . Trans. Amer. Math. Soc., 279(1), 113-124, 1983.
  • [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.
  • [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.
  • [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.
  • [33] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56, 121-155, 1976.
  • [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.
  • [35] J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., 195(910), viii+100, 2008.
  • [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.
  • [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.
  • [38] F. Göring, C. Helmberg, and M. Wappler. Embedded in the shadow of the separator. SIAM J. Optim., 19(1), 472-501, 2008.
  • [39] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1), 73-146, 2003.[Crossref]
  • [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.
  • [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.
  • [43] I. Haviv and O. Regev. The Euclidean distortion of flat tori. J. Topol. Anal., 5(2), 205-223, 2013.
  • [44] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.[Crossref]
  • [45] T. Hytönen and A. Naor. Pisier’s inequality revisited. Studia Math., 215(3), 221-235, 2013.
  • [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.
  • [49] G. Kasparov and G. Yu. The coarse geometric Novikov conjecture and uniform convexity. Adv. Math., 206(1), 1-56, 2006.[Crossref]
  • [50] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4), 821-852, 2006.
  • [51] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fundam. Math., 22, 77-108, 1934.
  • [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.
  • [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.
  • [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.
  • [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]
  • [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.
  • [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.
  • [62] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1), 59-95, 2005.
  • [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.
  • [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.
  • [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]
  • [67] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3), 261-277, 1988.[Crossref]
  • [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.
  • [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.
  • [73] S. Mazur. Une remarque sur l’homéomorphie des champs fonctionels. Studia Math., 1, 83-85, 1929.
  • [74] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247-298, 2008. Preliminary version in SODA ’06.
  • [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.
  • [77] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1, 163-199, 2013.
  • [78] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2), 167-233, 2012.
  • [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]
  • [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.
  • [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.
  • [82] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552, 213-236, 2002.
  • [83] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Compos. Math., 147(5), 1546-1572, 2011.
  • [84] I. Newman and Y. Rabinovich. Hard metrics from Cayley graphs of abelian groups. Theory Comput., 5, 125-134, 2009.
  • [85] E. Odell and T. Schlumprecht. The distortion problem. Acta Math., 173(2), 259-281, 1994.
  • [86] S.-i. Ohta. Extending Lipschitz and Hölder maps between metric spaces. Positivity, 13(2), 407-425, 2009.[Crossref]
  • [87] S.-i. Ohta. Markov type of Alexandrov spaces of non-negative curvature. Mathematika, 55(1-2), 177-189, 2009.[Crossref]
  • [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.
  • [90] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4), 326-350, 1975.
  • [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.
  • [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.
  • [94] Y. Rabinovich. On average distortion of embedding metrics into the line. Discrete Comput. Geom., 39(4), 720-733, 2008.[Crossref]
  • [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.
  • [97] C. A. Rogers. A note on coverings and packings. J. London Math. Soc., 25, 327-331, 1950.
  • [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]
  • [99] M. Talagrand. An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities. Proc. Amer.Math. Soc., 104(3), 905-909, 1988.[Crossref]
  • [100] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_agms-2014-0001
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.