[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Normalized Laplacian Eigenvalues of Hypergraphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In this paper, we give tight bounds for the normalized Laplacian eigenvalues of hypergraphs that are not necessarily uniform, and provide an edge version interlacing theorem, a Cheeger inequality, and a discrepancy inequality that are related to the normalized Laplacian eigenvalues for uniform hypergraphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data Availability

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

  1. Mulas, R.: A Cheeger cut for uniform hypergraphs. Graphs Combin. 37, 2265–2286 (2021)

    Article  MathSciNet  Google Scholar 

  2. Banerjee, A.: On the spectrum of hypergraphs. Linear Algebra Appl. 614, 82–110 (2021)

  3. Feng, K., Li, W.-C.: Spectra of hypergraphs and applications. J. Number Theory 60, 1–22 (1996)

    Article  MathSciNet  Google Scholar 

  4. Saha, S.S., Sharma, K., Panda, S.K.: On the Laplacian spectrum of \(k\)-uniform hypergraphs. Linear Algebra Appl. 655, 1–27 (2022)

    Article  MathSciNet  Google Scholar 

  5. Chung, F.R.K.: Spectral Graph Theory. American Mathematical Society, Providence (1997)

    Google Scholar 

  6. Chen, G., Davis, G., Hall, F., Li, Z., Patel, K., Stewart, M.: An interlacing result on normalized Laplacians. SIAM J. Discrete Math. 18, 353–361 (2004)

    Article  MathSciNet  Google Scholar 

  7. Butler, S.: Interlacing for weighted graphs using the normalized Laplacian. Electron. J. Linear Algebra 16, 90–98 (2007)

    Article  MathSciNet  Google Scholar 

  8. Horak, D., Jost, J.: Interlacing inequalities for eigenvalues of discrete Laplace operators. Ann. Global Anal. Geom. 43, 177–207 (2013)

    Article  MathSciNet  Google Scholar 

  9. Alon, N., Milman, V.: \(\lambda _1\), isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38, 73–88 (1985)

    Article  MathSciNet  Google Scholar 

  10. Chung, F.R.K.: Laplacians of graphs and Cheeger’s inequalities. In: Miklós, D., Sós, V.T., Szőnyi, T. (eds.) Combinatorics, Paul Erdős is Eighty. Bolyai Soc. Math. Stud., 2, vol. 2, pp. 295–352. János Bolyai Mathematical Society, Budapest (1996)

  11. Chung, F.R.K.: Discrete isoperimetric inequalities. In: Grigor’yan, A., Yau, S.T. (eds.) Surveys in Differential Geometry, vol. 9, pp. 53–82. International Press, Somerville (2004)

    Google Scholar 

  12. Mohar, B.: Isoperimetric numbers of graphs. J. Combin. Theory Ser. B 47, 274–291 (1989)

    Article  MathSciNet  Google Scholar 

  13. Mulas, R., Zhang, D.: Spectral theory of Laplace operators on oriented hypergraphs. Discrete Math. 344, 112372 (2021)

    Article  MathSciNet  Google Scholar 

  14. Bollobás, B., Scott, A.D.: Discrepancy in graphs and hypergraphs. In: Győri, E., Katona, G.O.H., Lovász, L. (eds.) More Sets, Graphs and Numbers, pp. 33–56. Springer, Berlin (2006)

    Chapter  Google Scholar 

  15. Chung, F.R.K.: Constructing random-like graphs. In: Bollobás, B. (ed.) Probabilistic Combinatorics and its Applications, pp. 21–55. American Mathematical Society, Providence (1991)

    Chapter  Google Scholar 

  16. Bollobás, B., Nikiforov, V.: Hermitian matrices and graphs: singular values and discrepancy. Discrete Math. 285, 17–32 (2004)

    Article  MathSciNet  Google Scholar 

  17. Li, J., Guo, J., Shiu, W.C.: Bounds on normalized Laplacian eigenvalues of graphs. J. Inequal. Appl. 2014, 316 (2014)

    Article  MathSciNet  Google Scholar 

  18. Chung, F.R.K.: Four proofs for the Cheeger inequality and graph partition algorithms. In: Ji, L., Liu, K., Yang, L., Yau, S.T. (eds.) Fourth International Congress of Chinese Mathematicians, AMS/IP Stud. Adv. Math., vol. 48, pp. 331–349. American Mathematical Society, Providence (2010)

Download references

Acknowledgements

The authors would like to thank the reviewers for constructive comments and suggestions.

Funding

This work was supported by the National Natural Science Foundation of China (No. 12071158).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, People’s Republic of China

    Leyou Xu & Bo Zhou

Authors
  1. Leyou Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bo Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bo Zhou.

Ethics declarations

Conflict of Interest

The authors have no relevant financial or non-financial interests to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, L., Zhou, B. Normalized Laplacian Eigenvalues of Hypergraphs. Graphs and Combinatorics 40, 92 (2024). https://doi.org/10.1007/s00373-024-02815-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-024-02815-3

Keywords

Mathematics Subject Classification