Abstract
The Cheeger constant is a measure of the edge expansion of a graph and as such plays a key role in combinatorics and theoretical computer science. In recent years, there is an interest in k-dimensional versions of the Cheeger constant that likewise provide quantitative measure of cohomological acyclicity of a complex in dimension k. In this paper, we study several aspects of the higher Cheeger constants. Our results include methods for bounding the cosystolic norm of k-cochains and the k-th Cheeger constants, with applications to the expansion of pseudomanifolds, Coxeter complexes and homogenous geometric lattices. We revisit a theorem of Gromov on the expansion of a product of a complex with a simplex and provide an elementary derivation of the expansion in a hypercube. We prove a lower bound on the maximal cosystole in a complex and an upper bound on the expansion of bounded degree complexes and give an essentially sharp estimate for the cosystolic norm of the Paley cochains. Finally, we discuss a non-abelian version of the one-dimensional expansion of a simplex, with an application to a question of Babson on bounded quotients of the fundamental group of a random 2-complex.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley-Intescience, New York (2000)
Babson, E., Hoffman, C., Kahle, M.: The fundamental group of random 2-complexes. J. Am. Math. Soc. 24, 1–28 (2011)
Chung, F.R.K.: Several generalizations of Weil sums. J. Number Theory 49, 95–106 (1994)
Dotterer, D., Kahle, M.: Coboundary expanders. J. Topol. Anal. 4, 499–514 (2012)
Edelsbrunner, H.: A short course in computational geometry and topology. In: SpringerBriefs in Applied Sciences and Technology. Springer (2014)
Farber, M., Gonzalez, J., Schütz, D.: Oberwolfach Arbeitsgemeinschaft: Topological Robotics. Report No. 47/2010 www.mfo.de/document/1041/OWR 2010 47.pdf. Accessed 1 Jan 2013
Folkman, J.: The homology groups of a lattice. J. Math. Mech. 15, 631–636 (1966)
Gromov, M.: Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20, 416–526 (2010)
Hoffman, C., Kahle, M., Paquette, E.: The threshold for integer homology in random d-complexes. Discrete Comput. Geom. 57, 810–823 (2017)
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. (N.S.) 43, 439–561 (2006)
Humphreys, J.E.: Reflection groups and Coxeter groups. In: Cambridge Studies in Advanced Mathematics, vol. 29. Cambridge University Press, Cambridge (1990)
Kozlov, D.N.: Combinatorial algebraic topology. In: Algorithms and Computation in Mathematics, vol. 21. Springer, Berlin (2008)
Kozlov, D.N.: The first Cheeger constant of a simplex. Graphs Combin. To appear arXiv:1610.07136
Linial, N., Meshulam, R.: Homological connectivity of random 2-complexes. Combinatorica 26, 475–487 (2006)
Lubotzky, A.: Expander graphs in pure and applied mathematics. Bull. Am. Math. Soc. (N.S.) 49, 113–162 (2012)
Lubotzky, A., Meshulam, R.: Random Latin squares and 2-dimensional expanders. Adv. Math. 272, 743–760 (2015)
Lubotzky, A., Meshulam, R., Mozes, S.: Expansion of building-like complexes. Groups Geom. Dyn. 10, 155–175 (2016)
Łuczak, T., Peled, Y.: Integral homology of random simplicial complexes. arXiv:1607.06985
McDiarmid, C.: On the method of bounded differences. Surv. Comb. 141, 148–188 (1989)
Meshulam, R., Wallach, N.: Homological connectivity of random \(k\)-dimensional complexes. Random Struct. Algorithms 34, 408–417 (2009)
Olum, P.: Non-abelian cohomology and van Kampen’s theorem. Ann. Math. 68, 658–668 (1958)
Ronan, M.: Lectures on Buildings. Academic Press Inc., Boston (1989)
Steenbergen, J., Klivans, C., Mukherjee, S.: A Cheeger-type inequality on simplicial complexes. Adv. Appl. Math. 56, 56–77 (2014)
West, D.B.: Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River (1996)
Acknowlegements
This research was supported by the German-Israeli Foundation for Scientific Research, under Grant number 1261/14.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Kozlov, D.N., Meshulam, R. Quantitative aspects of acyclicity. Res Math Sci 6, 33 (2019). https://doi.org/10.1007/s40687-019-0195-z
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s40687-019-0195-z