Teaching-Liu


Home

Activities

Publications

Talks

Teaching

Research Seminars

Geometric analysis on graphs

Selected topics in geometric analysis (Fall 2021)


Notices

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).


Lectures and references

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+].


References list

Books

[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


Articles

[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.


Riemannian Geometry 2021 Spring


Differential Geometry 2020 Fall


Riemannian Geometry 2020 Spring


2017级华罗庚讨论班2019-2020


Differential Geometry 2019 Fall


Riemannian Geometry 2019 Spring


Differential Geometry 2018 Fall


纯粹数学前沿 2018 夏季学期


Riemannian Geometry 2018 Spring


Differential Geometry 2017 Fall


Riemannian Geometry 2017 Spring


Teaching in Durham