2. 2021/9/28: Detailed references and further reading materials added!

1. Lecture room 2604: 2(15:55-17:30); 4(14:00-15:35).

Lecture 1 Introduction; Harmonic functions on graphs.

Lecture 2 Laplacian; Courant's minimax principle; Bipartite graphs.

Lecture 3 Complete graphs; Diameter and the second eigenvalue.

Lecture 4 Examples of eigenvalue and eigenfunctions: cycles; Cartesian products; Hypercubes.

Lecture 5 Discrete nodal domain theorem.

Lecture 6 Islands of strong nodal domains.

Lecture 7 Vertex degree, graph genus and strong nodal domains.

Lecture 8 Convergence to equilibrium; Cheeger inequality.

Lecture 9 Distribution of random walks; dual Cheeger constant.

Lecture 10 Dual Cheeger inequality; Harary's balance Theorem.

Lecture 11 Zaslavsky's switching lemma; Signed Laplacian.

Lecture 12 Cheeger constant on signed graphs.

Lecture 13 Cheeger inequality on signed graphs; Multi-way Cheeger constants.

Lecture 14 Higher order Cheeger inequalities on signed graphs.

Lecture 15 Padded random partition.

Lecture 16 Metric and Measure doubling dimensions; Improved Cheeger inequality I.

Lecture 17 Improved Cheeger inequality II.

Lecture 18 Higher order Improved Cheeger inequality; Curvature for signed graphs.

Lecture 19 Heat semigroups and related characterization of curvature on signed graphs.

Lecture 20 Buser type inequalities and eigenvalue ratio estimates.

Lecture 21 Lichnerowicz estimate; Normalized heat diffusion.

Lecture 22 Nica Theorem; Heat kernel on infinite graphs.

Lecture 23 Dirichlet heat kernel; Exhaustion via finite connected subgraphs.

Lecture 24 Convergence to the kernel of operator exponential.

Lecture 25 Stochastic completeness.

Lecture 26 Curvature revisited: lower bound; Ricci flat graphs.

Lecture 27 Gradient estimate; Stochatic completeness revisited; Diameter bounds.

Lecture 28 Rigidity properties of the hypercube: curvature and distance function.

Lecture 29 Eigenvalue sharpness and distance function; Hypercube shell structure (I).

Lecture 30 Hypercube shell structure (II); Small sphere and non-clustering properties

Lecture 31 Graphs satisfying HSS+regularity+SSP+NCP are hypercubes

Ref. 1. [JJ1, Chap. 1 and 5], [DK, Commentary, Chap. VI §1], [DS, Lecture 12].

Ref. 2. [JJ2, Chap. 2].

Ref. 3. [FC, §1.1-1.4 ], [Nilli91], [Murty03].

Ref. 4. [AG, §2.6, 2.7, 2.9, 3.3], [BLS, §3.1], [Friedman93].

Ref. 5. [BLS, §3.2], [DGLS01], [SY, Chapt III §6].

Ref. 6. [BLS, §3.4], [LLMY10].

Ref. 7. [LLMY10], [Youngs63].

Ref. 8. [BLS, §1.6], [AG, §2.3, 3.1], [LOT14, Lemma 2.2].

Ref. 9. [AG, §1.3, 2.3, 2.5], [DR94], [BJ13], [Trevisan12].

Ref. 10. [Trevisan12], [Harary54].

Ref. 11. [Zaslavsky10], [AL20].

Ref. 12. [AL20], [LMP19, Theorem 4.2].

Ref. 13. [AL20].

Ref. 14. [AL20], [LLPP15, §5.3].

Ref. 15. [GKL03].

Ref. 16. [AL20].

Ref. 17. [AL20], [KLLOT13]

Ref. 18. [AL20], [LMP19].

Ref. 19. [LMP19].

Ref. 20. [LMP19].

Ref. 21. [Nica20],[RS16].

Ref. 22. [Nica20],[W07],[DM06].

Ref. 23. [W07],[Dodziuk83],[Weber10].

Ref. 24. [W07, Chap. 2],[Dodziuk83],[Weber10].

Ref. 25. [W07, §3.1,3.6].

Ref. 26. [LY10],[JL14],[Sch98].

Ref. 27. [HL17],[LMP18].

Ref. 28. [LMP17+], [CKLP21+].

Ref. 29. [LMP17+], [CKLP21+].

Ref. 30. [LMP17+], [CKLP21+].

Ref. 30. [LMP17+].

[AG] Alexander Grigor'yan, Introduction to Analysis on graphs, University Lecture Series vol. 71, AMS, 2018. Preprint on Prof. Grigor'yan's homepage.

[BLS] Türker Bıyıkoğlu, Josef Leydold, Peter F. Stadler, Laplacian Eigenvectors of Graphs, Lecture Notes in Mathematics 1915, Springer, 2007.

[DK] Dénes König, Theory of Finite and Infinite Graphs, with a commentary by W. T. Tutte, Birkhäuser, 1990. (originally published in German in 1936 by Akademische Verlagsgesellschaft Leipzig.)

[DS] Daniel A. Spielman, Lecture notes of "Graphs and Networks", Fall 2010.

[FC] Fan R. K. Chung, Spectral graph theory, CBMS Number 92, AMS, 1997. Revised version on Prof. Chung's homepage

[JJ1] Jürgen Jost, Mathematical concepts, Springer, 2015.

[JJ2] Jürgen Jost, Mathematical methods in biology and neurobiology, Universitext, Springer, 2014.

[KLW] Matthias Keller, Daniel Lenz, Radosław Wojciechowski, Graphs and discrete Dirichlet spaces, GMW 358, Springer, 2021. Preprint on Prof. Keller's homepage.

[SY] Richard Schoen, Shing-Tung Yau, Lectures on differential geometry, International Press, 1994.

[W07] Radosław Wojciechowski, Stochastic completeness of graphs, PhD Thesis, 2007. arXiv

[AL20] F. M. Atay, S. Liu, Cheeger constants, structural balance, and spectral clustering analysis for signed graphs, Discrete Math. 343 (2020), 111616.

[BJ13] F. Bauer, J. Jost, Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian, Comm. Anal. Geom. 21 (2013), no. 4, 787-845.

[CKLP21+] D. Cushing, S. Kamtue, S. Liu, N. Peyerimhoff, Bakry-Émery curvature on graphs as an eigenvalue problem, Calc. Var. accepted, arXiv: 2102.08687.

[LLPP15] C. Lange, S. Liu, N. Peyerimhoff, O. Post, Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians, Calc. Var. 54 (2015), 4165-4196.

[DGLS01] E. B. Davies, G. M. L. Gladwell, J. Leydold, P. F. Stadler, Discrete nodal domain theorems, Lin. Algebra Appl. 336 (2001), 51-60.

[DR94] M. Desai, V. Rao, A characterization of the smallest eigenvalue of a graph, J. Graph Theory 18 (1994), no. 2, 181-194.

[Dodziuk83] J. Dodziuk, Maximum principle for parabolic inequalities and the heat flow on open manifolds, Indiana Univ. Math. J. 32 (1983), no. 5, 703-716.

[DM06] J. Dodziuk, V. Mathai, Kato's inequality and asymptotic spectral properties for discrete magnetic Laplacians, The uniquitous heat kernel, 69-81, Contemp. Math. 398 (2006), AMS, Providence, RI.

[Friedman93] J. Friedman, Some geometric aspect of graphs and their eigenfunctions, Duke Math. J. 69 (1993), 485-525.

[GKL03] A. Gupta, R. Krauthgamer, J. R. Lee, Bounded geometries, fractals, and low-distortion embeddings, 44th Symposium on Foundations of Computer Sciences (2003), 177-207.

[Harary54] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953/54), 143-146.

[HL17] B. Hua, Y. Lin, Stochastic completeness for graphs with curvature dimension conditions. Adv. Math. 306 (2017), 279-302.

[JL14] J. Jost, S. Liu, Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs, Discrete Comput. Geom. 51 (2014), no. 2, 300-322.

[KLLOT13] T.-C. Kwok, L.-C. Lau, Y.-T. Lee, S. Oveis Gharan, L. Trevisan, Improved Cheeger's inequality: Analysis of spectral partitioning algorithms through higher order spectral gap, STOC' 13 (2013), 11-20, ACM, New York.

[LOT14] J. R. Lee, S. Oveis Gharan, L. Trevisan, Multiway spectral partitioning and higher-order Cheeger inequalities, J. ACM 61 (2014), no.6, Art. 37, 30pp.

[LLMY10] Y. Lin, G. Lippner, D. Mangoubi, S.-T. Yau, Nodal geometry of graphs on surfaces, Discrete Contin. Dyn. Syst. 28 (2010), no. 3, 1291–1298.

[LY10] Y. Lin, S.-T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), no. 2, 343–356.

[LMP18] S. Liu, F. Münch, N. Peyerimhoff, Bakry-Émery curvature and diameter bounds on graphs. Calc. Var. 57 (2018), Art. 67.

[LMP19] S. Liu, F. Münch, N. Peyerimhoff, Curvature and higher order Buser inequalities for the graph connection Laplacian, SIAM J. Discrete Math. 33 (2019), no.1, 257-305.

[LMP17+] S. Liu, F. Münch, N. Peyerimhoff, Rigidity properties of the hypercube via Bakry-Émery curvature, arXiv:1705.06789.

[Murty03] M. Ram Murty, Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003), no.1, 1-20.

[Nica20] B. Nica, A note on normalized heat diffusion for graphs, Bull. Aust. Math. Soc. 102 (2020), 1-6.

[Nilli91] A. Nilli, On the second eigenvalue of a graph, Discrete Math. 91 (1991), 207-210.

[RS12] O. Regev, I. Shinkar, A counterexample to monotonicity of relative mass in random walks, Electron. Commun. Probab. 21 (2016), no. 8, 1-8.

[Sch98] M. Schmuckenschläger, Curvature of nonlocal Markov generators, Convex geometric analysis (Berkeley, CA, 1996), 189–197, Math. Sci. Res. Inst. Publ. 34, Cambridge Univ. Press, Cambridge, 1999.

[Trevisan12] L. Trevisan, Max cut and the smallest eigenvalue, SIAM J. Comput. 41 (2012), no. 6, 1769-1786.

[Weber10] A. Weber, Analysis of the physical Laplacian and the heat flow on a locally fintie graph, J. Math. Anal. Appl. 370 (2010), 146-158.

[Youngs63] J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303-315.

[Zaslavsky10] T. Zaslavsky, Matrices in the theory of signed simple graphs, Ramanujan Math. Soc. Lect. Notes Ser. 13 (2010), 207-229.