×

zbMATH — the first resource for mathematics

The theta number of simplicial complexes. (English) Zbl 1419.90109
Summary: We introduce a generalization of the celebrated Lovász theta number of a graph to simplicial complexes of arbitrary dimension. Our generalization takes advantage of real simplicial cohomology theory, in particular combinatorial Laplacians, and provides a semidefinite programming upper bound of the independence number of a simplicial complex. We consider properties of the graph theta number such as the relationship to Hoffman’s ratio bound and to the chromatic number and study how they extend to higher dimensions. Like in the case of graphs, the higher dimensional theta number can be extended to a hierarchy of semidefinite programming upper bounds reaching the independence number. We analyze the value of the theta number and of the hierarchy for dense random simplicial complexes.

MSC:
90C35 Programming involving graphs or networks
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] M. Anjos and J. B. Lasserre, Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, Vol. 166, Springer, New York, 2012. · Zbl 1235.90002
[2] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization, MPS/SIAM Series on Optimization, Society for Industrial and Applied Mathematics, Philadelphia, PA; Mathematical Programming Society, Philadelphia, PA, 2001. · Zbl 0986.90032
[3] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. · Zbl 1058.90049
[4] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Univesitext, Springer, New York, 2012. · Zbl 1231.05001
[5] Cohn, H.; Kumar, A.; Miller, S. D.; Radchenko, D.; Viazovska, M. S., The sphere packing problem in dimension 24, Annals of Mathematics, 185, 1017-1033, (2017) · Zbl 1370.52037
[6] Coja-Oghlan, A., The Lovász number of random graphs, Combinatorics, Probability and Computing, 14, 439-465, (2005) · Zbl 1076.05072
[7] Corte, P. E B.; Laat, D.; Vallentin, F., Fourier analysis on finite groups and the Lovász theta-number of Cayley graphs, Experimental Mathematics, 23, 146-152, (2014) · Zbl 1296.05120
[8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Journal of Research 10(1973). · Zbl 1075.05606
[9] Dotterrer, D.; Kaufman, T.; Wagner, U., On expansion and topological overlap, Geometriae Dedicata, 195, 3017-317, (2018) · Zbl 1393.05315
[10] Dotterrer, D.; Guth, L.; Kahle, M., 2-complexes with large 2-girth, Discrete & Computational Geometry, 59, 383-412, (2018) · Zbl 1381.05066
[11] Duval, A. M.; Klivans, C. J.; Martin, J. L., Simplicial and cellular trees, 713-752, (2016), Cham · Zbl 1354.05151
[12] Ellis, D.; Friedgut, E.; Pilpel, H., Intersecting families of permutations, Journal of the American Mathematical Society, 24, 649-682, (2011) · Zbl 1285.05171
[13] Ellis, D.; Filmus, Y.; Friedgut, E., Triangle-intersecting families of graphs, Journal of the European Mathematical Society, 14, 841-885, (2012) · Zbl 1238.05143
[14] Evra, S.; Golubev, K.; Lubotzky, A., Mixing properties and the chromatic number of Ramanujan complexes, International Mathematics Research Notices, 22, 11520-11548, (2015) · Zbl 1328.05208
[15] S. Evra and T. Kaufman, Bounded degree cosystolic expanders of every dimension, in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 36-48. · Zbl 1376.05095
[16] Feige, U.; Ofek, E., Spectral techniques applied to sparse random graphs, Random Structures & Algorithms, 27, 251-275, (2005) · Zbl 1076.05073
[17] Garland, H., p-adic curvature and the cohomology of discrete subgroups of p-adic groups, Annals of Mathematics, 97, 375-423, (1973) · Zbl 0262.22010
[18] B. Gärtner and J. Matoušek, Approximation Algorithms and Semidefinite Programming, Springer, Heidelberg, 2012. · Zbl 1257.90001
[19] Golubev, K., On the chromatic number of a simplicial complex, Combinatorica, 37, 953-964, (2017) · Zbl 1399.05227
[20] Gromov, M., Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geometric and Functional Analysis, 20, 416-526, (2010) · Zbl 1251.05039
[21] Gundert, A.; Wagner, U., On eigenvalues of random complexes, Israel Journal of Mathematics, 216, 545-582, (2016) · Zbl 1353.05079
[22] C. Hoffman, M. Kahle and E. Paquette, Spectral gaps of random graphs and applications to random topology, arXiv.math:1201.0425.
[23] Horak, D.; Jost, J., Spectra of combinatorial Laplace operators on simplicial complexes, Advances in Mathematics, 244, 303-336, (2013) · Zbl 1290.05103
[24] Juhász, F., The aymptotic behaviour of Lovász theta function for random graphs, Combinatorica, 2, 153-155, (1982) · Zbl 0526.05050
[25] Kahle, M., CRC, Boca Raton, FL, 581-603, (2017)
[26] Kalai, G., Enumeration of ℚ-acyclic simplicial complexes, Israel Journal of Mathematics, 45, 337-351, (1983) · Zbl 0535.57011
[27] Kaufman, T.; Kazhdan, D.; Lubotzky, A., Isoperimetric inequalities for Ramanujan complexes and topological expanders, Geometric and Functional Analysis, 26, 250-287, (2016) · Zbl 1339.05075
[28] Krivelevich, M.; Sudakov, B., The chromatic numbers of random hypergraphs, Random Structures & Algorithms, 12, 381-403, (1998) · Zbl 0959.05110
[29] Lasserre, J. B., An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM Journal on Optimization, 12, 756-769, (2002) · Zbl 1007.90046
[30] Laurent, M., A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxationsfor 0-1 programming, Mathematics of Operations Research, 28, 470-496, (2003) · Zbl 1082.90084
[31] Linial, N.; Meshulam, R., Homological connectivity of random 2-complexes, Combinatorica, 26, 475-487, (2006) · Zbl 1121.55013
[32] Lovász, L., On the Shannon capacity of a graph, IEEE Transactions on Information Theory, 25, 1-7, (1979) · Zbl 0395.94021
[33] Lubotzky, A., Ramanujan complexes and high dimensional expanders, Japanese Journal of Mathematics, 9, 137-169, (2014) · Zbl 1302.05095
[34] Lubotzky, A.; Meshulam, R., A Moore bound for simplicial complexes, Bulletin of the London Mathematical Society, 39, 353-358, (2007) · Zbl 1180.13028
[35] Matouşek, J.; Tancer, M.; Wagner, U., Hardness of embedding simplicial complexes in ℝ\(d\), Journal of the European Mathematical Society, 13, 259-295, (2011) · Zbl 1208.68130
[36] Oliveira Filho, F. M.; Vallentin, F., Computing upper bounds for packing densities of congruent copies of a convex body, 155-188, (2018), Berlin-Heidelberg · Zbl 1423.52035
[37] Parzanchevski, O.; Rosenthal, R., Simplicial complexes: Spectrum, homology and random walks, Random Structures & Algorithms, 50, 225-261, (2017) · Zbl 1359.05114
[38] Parzanchevski, O.; Rosenthal, R.; Tessler, R. J., Isoperimetric inequalities in simplicial complexes, Combinatorica, 36, 195-227, (2016) · Zbl 1389.05174
[39] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Review, 38, 49-95, (1996) · Zbl 0845.65023
[40] Viazovska, M. S., The sphere packing problem in dimension 8, Annals of Mathematics, 185, 991-1015, (2017) · Zbl 1373.52025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.