On the first and second eigenvalue of finite and infinite uniform hypergraphs

Li, Hong-Hai; Mohar, Bojan

doi:10.1090/proc/14274

On the first and second eigenvalue of finite and infinite uniform hypergraphs
HTML articles powered by AMS MathViewer

by Hong-Hai Li and Bojan Mohar

Proc. Amer. Math. Soc. 147 (2019), 933-946

DOI: https://doi.org/10.1090/proc/14274

Published electronically: November 16, 2018

PDF | Request permission

Abstract:

Lower bounds for the first and the second eigenvalue of uniform regular hypergraphs are obtained. One of these bounds is a generalization of the Alon–Boppana Theorem to hypergraphs.

References

N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR 875835, DOI 10.1007/BF02579166
Changjiang Bu, Xu Zhang, Jiang Zhou, Wenzhe Wang, and Yimin Wei, The inverse, rank and product of tensors, Linear Algebra Appl. 446 (2014), 269–280. MR 3163144, DOI 10.1016/j.laa.2013.12.015
Umit V. Catalyurek and Cevdet Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, Parallel and Distributed Systems, IEEE Transactions 10(7) (1999), 673–693.
Kungching Chang, Liqun Qi, and Tan Zhang, A survey on the spectral theory of nonnegative tensors, Numer. Linear Algebra Appl. 20 (2013), no. 6, 891–912. MR 3141883, DOI 10.1002/nla.1902
Fan R. K. Chung, The Laplacian of a hypergraph, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 21–36. MR 1235565, DOI 10.1090/dimacs/010/03
Joshua Cooper and Aaron Dutle, Spectra of uniform hypergraphs, Linear Algebra Appl. 436 (2012), no. 9, 3268–3292. MR 2900714, DOI 10.1016/j.laa.2011.11.018
Keqin Feng and Wen-Ch’ing Winnie Li, Spectra of hypergraphs and applications, J. Number Theory 60 (1996), no. 1, 1–22. MR 1405722, DOI 10.1006/jnth.1996.0109
Joel Friedman, The spectra of infinite hypertrees, SIAM J. Comput. 20 (1991), no. 5, 951–961. MR 1115660, DOI 10.1137/0220058
Joel Friedman and Avi Wigderson, On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), no. 1, 43–65. MR 1325271, DOI 10.1007/BF01294459
Shenglong Hu and Liqun Qi, The Laplacian of a uniform hypergraph, J. Comb. Optim. 29 (2015), no. 2, 331–366. MR 3297926, DOI 10.1007/s10878-013-9596-x
L. Kang, V. Nikiforov, and X. Yuan, The $p$-spectral radius of $k$-partite and $k$-chromatic uniform hypergraphs, Linear Algebra Appl. 478 (2015), 81–107. MR 3342416, DOI 10.1016/j.laa.2015.03.016
Peter Keevash, John Lenz, and Dhruv Mubayi, Spectral extremal problems for hypergraphs, SIAM J. Discrete Math. 28 (2014), no. 4, 1838–1854. MR 3270186, DOI 10.1137/130929370
Mike Krebs and Anthony Shaheen, Expander families and Cayley graphs, Oxford University Press, Oxford, 2011. A beginner’s guide. MR 3137611
John Lenz and Dhruv Mubayi, Eigenvalues of non-regular linear quasirandom hypergraphs, Discrete Math. 340 (2017), no. 2, 145–153. MR 3578811, DOI 10.1016/j.disc.2016.07.024
John Lenz and Dhruv Mubayi, Eigenvalues and linear quasirandom hypergraphs, Forum Math. Sigma 3 (2015), Paper No. e2, 26. MR 3324939, DOI 10.1017/fms.2014.22
L.-H. Lim, Singular values and eigenvalues of tensors: a variational approach, in: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP’05), vol. 1, 2005, pp. 129–132.
Linyuan Lu and Xing Peng, High-ordered random walks and generalized Laplacians on hypergraphs, Algorithms and models for the web graph, Lecture Notes in Comput. Sci., vol. 6732, Springer, Heidelberg, 2011, pp. 14–25. MR 2842309, DOI 10.1007/978-3-642-21286-4_{2}
Linyuan Lu and Xing Peng, Loose Laplacian spectra of random hypergraphs, Random Structures Algorithms 41 (2012), no. 4, 521–545. MR 2993134, DOI 10.1002/rsa.20443
María G. Martínez, Harold M. Stark, and Audrey A. Terras, Some Ramanujan hypergraphs associated to $\textrm {GL}(n,{\Bbb F}_q)$, Proc. Amer. Math. Soc. 129 (2001), no. 6, 1623–1629. MR 1814089, DOI 10.1090/S0002-9939-00-05965-7
Bojan Mohar, A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem, Proc. Amer. Math. Soc. 138 (2010), no. 11, 3899–3909. MR 2679612, DOI 10.1090/S0002-9939-2010-10543-9
Vladimir Nikiforov, Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014), 455–535. MR 3230456, DOI 10.1016/j.laa.2014.05.005
V. Nikiforov, Combinatorial methods for the spectral $p$-norm of hypermatrices, Linear Algebra Appl. 529 (2017), 324–354. MR 3659806, DOI 10.1016/j.laa.2017.04.023
A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), no. 2, 207–210. MR 1124768, DOI 10.1016/0012-365X(91)90112-F
Liqun Qi, Eigenvalues of a real supersymmetric tensor, J. Symbolic Comput. 40 (2005), no. 6, 1302–1324. MR 2178089, DOI 10.1016/j.jsc.2005.05.007
Jia-Yu Shao, A general product of tensors with applications, Linear Algebra Appl. 439 (2013), no. 8, 2350–2366. MR 3091308, DOI 10.1016/j.laa.2013.07.010
Jean-Pierre Serre, Répartition asymptotique des valeurs propres de l’opérateur de Hecke $T_p$, J. Amer. Math. Soc. 10 (1997), no. 1, 75–102 (French). MR 1396897, DOI 10.1090/S0894-0347-97-00220-8