×

Spectrum of signless 1-Laplacian on simplicial complexes. (English) Zbl 1441.05254

Summary: We introduce the signless 1-Laplacian and the dual Cheeger constant on simplicial complexes. The connection of its spectrum to the combinatorial properties like independence number, chromatic number and dual Cheeger constant is investigated. Our estimates can be comparable to Hoffman’s bounds on Laplacian eigenvalues of simplicial complexes. An interesting inequality involving multiplicity of the largest eigenvalue, independence number and chromatic number is provided, which could be regarded as a variant version of Lovász sandwich theorem. Also, the behavior of 1-Laplacian under the topological operations of wedge and duplication of motifs is studied. The Courant nodal domain theorem in spectral theory is extended to the setting of signless 1-Laplacian on complexes.

MSC:

05E45 Combinatorial aspects of simplicial complexes
47J10 Nonlinear spectral theory, nonlinear eigenvalue problems
49R05 Variational methods for eigenvalues of operators
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Naneh Apkarian, Spectral Bounds on the Chromatic Number, 2013
[2] Christine Bachoc, Anna Gundert and Alberto Passuello, The theta number of simplicial complexes, Israel Journal of Mathematics, 232 (2019), 443-481. · Zbl 1419.90109
[3] Frank H Clarke, Optimization and Nonsmooth Analysis, Wiley New York, 1983. · Zbl 0582.49001
[4] Kung-Ching Chang, Sihong Shao and Dong Zhang, Spectrum of the signless 1Laplacian and the dual Cheeger constant on graphs,arXiv:1607.00489.
[5] Kung-Ching Chang, Spectrum of the 1-laplacian and Cheeger’s constant on graphs, Journal of Graph Theory, 81 (2016), 167-207. · Zbl 1336.05084
[6] Kung-Ching Chang, Sihong Shao and Dong Zhang, The 1-Laplacian Cheeger cut: theory and algorithms, Journal of Computational Mathematics, 33 (2015), 443-467. · Zbl 1349.05203
[7] Kung-Ching Chang, Sihong Shao and Dong Zhang, Nodal domains of eigenvectors for 1-Laplacian on graphs, Advances in Mathematics, 308 (2017), 529-574. · Zbl 1366.35204
[8] Kung-Ching Chang, Critical Point Theory and Its Applications (in Chinese), Shanghai Science and Technology Press, 1985. · Zbl 0609.58001
[9] Shai Evra, Konstantin Golubev and Alexander Lubotzky, Mixing properties and the chromatic number of ramanujan complexes. International Mathematics Research Notices, (2015) 11520-11548. · Zbl 1328.05208
[10] Beno Eckmann, Harmonische funktionen und randwertaufgaben in einem komplex, Commentarii Mathematici Helvetici, 17 (1944), 240-255. · Zbl 0061.41106
[11] Konstantin Golubev, On the chromatic number of a simplicial complex. Combinatorica, 37 (2017), 953-964. · Zbl 1399.05227
[12] Danijela Horak and J¨urgen Jost, Interlacing inequalities for eigenvalues of discrete Laplace operators, Annals of Global Analysis and Geometry, 43 (2013), 177-207. · Zbl 1276.05129
[13] Danijela Horak and J¨urgen Jost, Spectra of combinatorial Laplace operators on simplicial conplexes, Advances in Mathematics, 244 (2013), 303-336. · Zbl 1290.05103
[14] Alan J Hoffman, On eigenvalues and colorings of graphs, b. harris ed., graph theory and its applications, 1970.
[15] Alan J Hoffman, On eigenvalues and colorings of graphs. In Selected Papers Of Alan J Hoffman: With Commentary, pages 407-419. World Scientific, 2003. · Zbl 1041.01013
[16] Matthias Hein and Thomas B¨uhler, An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. InAdvances in Neural Information Processing Systems 23, pages 847-855, 2010.
[17] Tali Kaufman and Alexander Lubotzky, High dimensional expanders and property testing. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 501-506, 2014. · Zbl 1365.68462
[18] Tali Kaufman and Izhar Oppenheim, High order random walks: Beyond spectral gap.arXiv:1707.02799, 2017. · Zbl 1428.68324
[19] Michael Krivelevich and Benny Sudakov, The chromatic numbers of random hypergraphs, Random Structures & Algorithms, 12 (1998), 381-403. · Zbl 0959.05110
[20] Alexander Lubotzky, Ramanujan complexes and high dimensional expanders, Japanese Journal of Mathematics, 9 (2014), 137-169. · Zbl 1302.05095
[21] Alexander Lubotzky, High dimensional expanders.arXiv:1712.02526. · Zbl 1302.05095
[22] Alexander Lubotzky and Ori Parzanchevski, From ramanujan graphs to ramanujan complexes. Philosophical Transactions of the Royal Society A, 378(2163):20180445, 2020. · Zbl 1462.05235
[23] Vladimir Nikiforov, Hoffman’s bound for hypergraphs.arXiv:1908.01433, 2019.
[24] Ori Parzanchevski and Ron Rosenthal, Simplicial complexes: spectrum, homology and random walks. Random Structures & Algorithms, 50 (2017), 225-261. · Zbl 1359.05114
[25] Paul Henry Rabinowitz, Minimax Methods in Critical Point Theory with Applications in Differential Equations, American Mathematical Society, 1986. · Zbl 0609.58002
[26] Pawel Wocjan and Clive Elphick, New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix, The Electronic Journal of Combinatorics, 20(3) #P39 (2013). · Zbl 1295.05112
[27] Dong Zhang, Topological multiplicity of the maximum eigenvalue of graph 1Laplacian, Discrete Mathematics, 341 (2018), 25-32. · Zbl 1372.05133
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.