Anybody who has ever read a mathematical text of the author would agree that his way of presenting complex material is nothing short of marvelous. This new book showcases again the author's unique ability of presenting challenging topics in a clear and accessible manner, and of guiding the reader with ease to a deep understanding of the subject.

—Matthias Keller, University of Potsdam

A central object of this book is the discrete Laplace operator on finite and infinite graphs. The eigenvalues of the discrete Laplace operator have long been used in graph theory as a convenient tool for understanding the structure of complex graphs. They can also be used in order to estimate the rate of convergence to equilibrium of a random walk (Markov chain) on finite graphs. For infinite graphs, a study of the heat kernel allows to solve the type problem—a problem of deciding whether the random walk is recurrent or transient.

This book starts with elementary properties of the eigenvalues on finite graphs, continues with their estimates and applications, and concludes with heat kernel estimates on infinite graphs and their application to the type problem.

The book is suitable for beginners in the subject and accessible to undergraduate and graduate students with a background in linear algebra I and analysis I. It is based on a lecture course taught by the author and includes a wide variety of exercises. The book will help the reader to reach a level of understanding sufficient to start pursuing research in this exciting area.

Readership

Undergraduate and graduate students and researchers interested in random walks on graphs and groups.

• Alexopoulos G.K., A lower estimate for central probabilities on polycyclic groups, Can. J. Math., 44 (1992) 897-910.
• Alon N., Milman V.D., $\lambda _1$ isoperimetric inequalities for graphs and superconcentrators, J. Comb. Theory B, 38 (1985) 73-88.
• Auscher P., Coulhon T., Grigor’yan A., ed., “Heat kernels and analysis on manifolds, graphs, and metric spaces”, Contem. Math. 338, AMS, Providence, RI, 2003.
• Babson E., Barcelo H., de Longueville M., Laubenbacher R., Homotopy theory of graphs, J. Algebr. Comb., 24 (2006) 31–44.
• Bachoc C., DeCorte E., de Oliveira Filho F.M., Vallentin F., Spectral bounds for the independence ratio and the chromatic number of an operator, Israel J. Math, 202 (2014) 227–254.
• Band R., Oren I., Smilansky U., Nodal domains on graphs - how to count them and why?, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 5–27.
• Barcelo H., Capraro V., White J.A., Discrete homology theory for metric spaces, Bull. London Math. Soc., 46 (2014) 889–905.
• Barlow M.T., Diffusions on fractals, in: “Lectures on Probability Theory and Statistics, Ecole d’été de Probabilités de Saint-Flour XXV - 1995”, Lecture Notes Math. 1690, Springer, 1998. 1-121.
• Barlow M.T., Which values of the volume growth and escape time exponent are possible for graphs?, Rev. Mat. Iberoam., 40 (2004) 1-31.
• Barlow M.T., “Random walks and heat kernels on graphs”, LMS Lecture Note Series 438, Cambridge Univ. Press, 2017.
• Barlow M.T., Bass R.F., Stability of parabolic Harnack inequalites, Trans. Amer. Math. Soc., 356 (2004) 1501–1533.
• Barlow M.T., Bass R.F., Kumagai T., Parabolic Harnack inequality and heat kernel estimates for random walks with long range jumps, Math. Z., 261 (2009) 297-320.
• Barlow M.T., Coulhon T., Grigor’yan A., Manifolds and graphs with slow heat kernel decay, Invent. Math., 144 (2001) 609-649.
• Barlow M.T., Coulhon T., Kumagai T., Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs, Comm. Pure Appl. Math., 58 (2005) 1642–1677.
• Barlow M.T., Perkins E.A., Symmetric Markov chains in $\Bbb {Z}^d$: how fast can they move?, Probab. Th. Rel. Fields, 82 (1989) 95–108.
• Bartholdi L., Grigorchuk R., Spectra of non-commutative dynamical systems and graphs related to fractal groups, C. R. Acad. Sci. Paris Ser. I Math. 331 (2000) 429–434.
• Bartholdi L., Grigorchuk R., Nekrashevych V., From fractal groups to fractal sets, in: “Fractals in Graz 2001”, Trends Math., Birkhäuser, Basel, 2003. 25–119.
• Bass H., The degree of polynomial growth of finitely generated groups, Proc. London Math. Soc., 25 (1972) 603–614.
• Bass H., The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math., 3 (1992) 717–797.
• Bauer F., Horn P., Lin Y., Lippner G., Mangoubi D., Yau S.-T., Li-Yau inequality on graphs, J. Diff. Geom., 99 (2015) 359–405.
• Bauer F., Hua B., Jost J., The dual Cheeger constant and spectra of infinite graphs, Adv. Math., 251 (2014) 147–194.
• Bauer F., Jost J., Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator, Comm. Anal. Geom., 21 (2013) 787–845.
• Bauer F., Jost J., Liu S., Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, Math. Res. Lett., 19 (2012) 1185–1205.
• von Below J., Can one hear the shape of a network?, in: “Partial differential equations on multistructures (Lumini 1999)”, Lecture Notes in Pure and Appl. Math. 219, Dekker, New York, 2001. 19–36.
• Bendikov A., Grigor’yan A., Pittet Ch., Woess W., Isotropic Markov semigroups on ultra-metric spaces, Russian Math. Surveys, 69 (2014) 589–680.
• Berkolaiko G., Carlson R., Fulling S., Kuchment P. ed., “Quantum graphs and their applications”, Contemp. Math. 415, AMS, Providence, RI, 2006.
• Berkolaiko G., Kuchment P., “Introduction to quantum graphs”, Mathematical Surveys and Monographs 186, AMS, Providence, RI, 2013.
• Berkolaiko G., A lower bound for nodal count on discrete and metric graphs, to appear in Commun. Math. Phys.
• Biggs N., “Algebraic graph theory”, Cambridge Univ. Press, 2001.
• Bıyıkoğlu T., Leydold J., Stadler P.F., “Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems”, Lecture Notes in Mathematics 1915, Springer, 2007.
• Bollobás, B., “Modern graph theory”, Graduate Texts in Mathematics 184, Springer, 1998.
• Carne K., A transmutation formula for Markov chains, Bull. Sci. Math., 109 (1985) 399-403.
• Cheng S.Y., Yau S.-T., Differential equations on Riemannian manifolds and their geometric applications, Comm. Pure Appl. Math., 28 (1975) 333-354.
• Chung F.R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2 (1989) 187-196.
• Chung F.R.K., “Spectral Graph Theory”, CBMS Regional Conference Series in Mathematics 92, AMS, Providence, RI, 1997.
• Chung F.R.K., Discrete isoperimetric inequalities, in: “Eigenvalues of Laplacians and other geometric operators”, Surveys in Differential Geometry IX, (2004) 53-82.
• Chung F.R.K., Faber V., Manteuffel Th. A., An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. of Discrete Math., 7 (1994) 443–457.
• Chung F.R.K., Graham R., “Erdös on graphs. His legacy of unsolved problems”, A K Peters, Ltd., Wellesley, MA, 1998.
• Chung F.R.K., Grigor’yan A., Yau S.-T., Upper bounds for eigenvalues of the discrete and continuous Laplace operators, Advances in Math., 117 (1996) 165-178.
• Chung F.R.K., Grigor’yan A., Yau S.-T., Eigenvalues and diameters for manifolds and graphs, in: “Tsinghua Lectures on Geometry and Analysis”, International Press, 1997. 79-105.
• Chung F.R.K., Lin Y., Yau S.-T., Harnack inequalities for graphs with non-negative Ricci curvature, J. Math. Anal. Appl, 415 (2014) 25–32.
• Chung F.R.K., Lu L., “Complex Graphs and Networks”, CBMS Regional Conference Series in Mathematics 107, AMS, Providence, RI, 2006.
• Chung F.R.K., Yau S.-T., Eigenvalue inequalities for graphs and convex subgraphs, Comm. in Analysis and Geom., 2 (1994) 628-639.
• Chung F.R.K., Yau, S.-T., Eigenvalues of graphs and Sobolev inequalities, Combinatorics, Probability and Computing, 4 (1995) 11-26.
• Colin de Verdière Y., “Spectres de graphes”, Cours Spécialisés 4, Société Mathématique de France, Paris, 1998.
• Coulhon T., Sobolev inequalities on graphs and manifolds, in: “Harmonic Analysis and Discrete Potential Theory”, Plenum Press, New York and London, 1992.
• Coulhon T., Grigor’yan A., On-diagonal lower bounds for heat kernels on non-compact manifolds and Markov chains, Duke Math. J., 89 (1997) 133-199.
• Coulhon T., Grigor’yan A., Random walks on graphs with regular volume growth, Geom. Funct. Anal., 8 (1998) 656-701.
• Coulhon T., Grigor’yan A., Pittet Ch., A geometric approach to on-diagonal heat kernel lower bounds on groups, Ann. Inst. Fourier, Grenoble, 51 (2001) 1763-1827.
• Coulhon T., Grigor’yan A., Zucca F., The discrete integral maximum principle and its applications, Tohoku Math. J., 57 (2005) 559-587.
• Coulhon T., Saloff-Coste L., Isopérimétrie pour les groupes et les variétés, Rev. Mat. Iberoam., 9 (1993) 293-314.
• Cvetkovic D., Doob M., Gutman I., Targasev A., “Recent results in the theory of graph spectra”, Ann. Disc. Math. 36, North Holland, 1988.
• Cvetkovic D., Doob M., Sachs H., “Spectra of graphs”, Acad. Press., NY, 1979.
• Davidoff G., Sarnak P., Valette A., “Elementary number theory, group theory and Ramanujan graphs”, Cambridge Univ. Press, 2003.
• Davies E.B., Large deviations for heat kernels on graphs, J. London Math. Soc. (2), 47 (1993) 65-72.
• Delmotte T., Parabolic Harnack inequality and estimates of Markov chains on graphs, Rev. Mat. Iberoam., 15 (1999) 181-232.
• Diaconis P., Saloff-Coste L., What do we know about the Metropolis Algorithm?, J. of Computer and System Sciences, 57 (1998) 20-36.
• Diaconis P., Stroock D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Prob., 1 (1991) 36-61.
• Diestel R., “Graph theory”, Graduate Texts in Mathematics 173, Springer, Berlin, 2017.
• Dimakis A., Müller-Hoissen F., Discrete differential calculus: graphs, topologies, and gauge theory, J. Math. Phys., 35 (1994) 6703-6735.
• Dodziuk J., Difference equations, isoperimetric inequalities and transience of certain random walks, Trans. Amer. Math. Soc., 284 (1984) 787-794.
• Dodziuk J., Kendall W.S., Combinatorial Laplacians and isoperimetric inequality, in: “From local times to global geometry, control and physics (Coventry, 1984/85)”, Pitman Res. Notes Math. Ser. 150, 1986. 68–74.
• Doyle P.G., Snell J.L., “Random walks and electric networks”, Carus Mathematical Monographs 22, Mathematical Association of America, Washington, DC, 1984.
• Exner P., Keating J.P., Kuchment P., Sunada T., Teplyaev A., ed., “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008.
• Figa-Talamanca A., “Harmonic analysis on free groups”, CRC, 1983.
• Figa-Talamanca A., Nebbia C., “Harmonic analysis and representation theory for groups acting on homogenous trees”, Cambridge Univ. Press, 1991.
• Friedlander L., Genericity of simple eigenvalues for a metric graph, Israel J. Math., 146 (2005) 149–156.
• Gaveau B., Okada M., Differential forms and heat diffusion on one-dimensional singular varieties, Bull. Sci. Math., 115 (1991) 61–80.
• Gaveau B., Okada M., Okada T., Explicit heat kernels on graphs and spectral analysis, in: “Several complex variables (Proceedings of the Mittag-Leffler Institute, Stockholm, 1987-88)”, Princeton Math. Notes 38, Princeton University Press, 1993. 364–388.
• Gieseker D., Knörrer H., Trubowitz E., “The geometry of algebraic Fermi curves”, Academic Press, Boston, 1992.
• Godsil C., Royle G., “Algebraic graph theory”, Graduate Texts in Mathematics 207, Springer, New York, 2001.
• Grigor’yan A., On the existence of positive fundamental solution of the Laplace equation on Riemannian manifolds, (in Russian) Matem. Sbornik, 128 (1985) 354-363. Engl. transl.: Math. USSR Sb., 56 (1987) 349-358.
• Grigor’yan A., Heat kernels on metric measure spaces, in: “Handbook of Geometric Analysis Vol. 2”, Ed. L. Ji, P. Li, R. Schoen, L. Simon, Advanced Lectures in Math. 13, International Press, 2010. 1-60.
• Grigor’yan A., Kelbert M., On Hardy-Littlewood inequality for Brownian motion on Riemannian manifolds, J. London Math. Soc. (2), 62 (2000) 625-639.
• Grigor’yan A., Lin Y., Muranov Yu., Yau S.-T., Homotopy theory for digraphs, Pure Appl. Math. Quaterly, 10 (2014) 619-674.
• Grigor’yan A., Lin Y., Muranov Yu., Yau S.-T., Path complexes and their homologies, to appear in Int. J. Math.
• Grigor’yan A., Muranov Yu., Yau S.-T., Graphs associated with simplicial complexes, Homology, Homotopy and Appl., 16 (2014) 295–311.
• Grigor’yan A., Muranov Yu., Yau S.-T., Cohomology of digraphs and (undirected) graphs, Asian J. Math., 19 (2015) 887-932.
• Grigor’yan A., Muranov Yu., Yau S.-T., On a cohomology of digraphs and Hochschild cohomology, J. Homotopy Relat. Struct., 11 (2016) 209–230.
• Grigor’yan A., Muranov Yu., Yau S.-T., Homologies of digraphs and Künneth formulas, Comm. Anal. Geom., 25 (2017) 969–1018.
• Grigor’yan A., Telcs A., Sub-Gaussian estimates of heat kernels on infinite graphs, Duke Math. J., 109 (2001) 451-510.
• Grigor’yan A., Telcs A., Harnack inequalities and sub-Gaussian estimates for random walks, Math. Ann., 324 (2002) 521-556.
• Grigorchuk R., Nekrashevych V., Self-similar groups, operator algebras and Schur complement, J. Modern Dynamics, 1 (2007) 323–370.
• Grigorchuk R., Sunik Z., Asymptotic aspects of Schreier graphs and Hanoi towers groups, C. R. Acad. Sci. Paris Ser. I Math. 342 (2006) 545–550.
• Grigorchuk R., Zuk A., The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps, in: “Random walks and geometry”, Walter de Gruyter, Berlin, 2004. 141–180.
• Grimmet J., “Probability on graphs: random Processes on graphs and lattices, 2nd edition”, Cambridge Univ. Press, 2017.
• Hambly B.M., Kumagai T., Heat kernel estimates and law of the iterated logarithm for symmetric random walks on fractal graphs, in: “Discrete geometric analysis”, Contemp. Math. 347, Amer. Math. Soc., Providence, RI, 2004. 153–172.
• Hambly B.M., Kumagai T., Heat kernel estimates for symmetric random walks on a class of fractal graphs and stability under rough isometries, in: “Fractal geometry and applications: a jubilee of Benoît Mandelbrot, Part 2” Proc. Sympos. Pure Math. 72 Part 2, Amer. Math. Soc., Providence, RI, 2004. 233–259.
• Hebisch W., Saloff-Coste, L., Gaussian estimates for Markov chains and random walks on groups, Ann. Prob., 21 (1993) 673–709.
• Higuchi Y., Nomura Y., Spectral structure of the Laplacian on a covering graph, European J. Combin., 30 (2009) 570–585.
• Hoffman A.J., On eigenvalues and colorings of graphs, in: “Graph Theory and its Applications”, Academic Press, New York, 1970. 79–91.
• Horton M.D., Stark H.M., Terras A.A., What are zeta functions of graphs and what are they good for?, in: “Quantum graphs and their applications”, Contemp. Math. 415, AMS, Providence, RI, 2006. 173–189.
• Horton M.D., Stark H.M., Terras A.A., Zeta functions of weighted and covering graphs, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 29–50.
• Hua B., Lin Y., Curvature notions on graphs, Front. Math. China, 11 (2016) 1275–1290.
• Hua B., Lin Y., Stochastic completeness for graphs with curvature dimension conditions, Adv. Math., 306 (2017) 279–302.
• Kaimanovich V.A., Vershik A.M., Random walks on discrete groups: boundary and entropy, Ann. Prob., 11 (1983) 457-490.
• Kaimanovich V.A., Woess W., The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality, Probab. Th. Rel. Fields, 91 (1992) 445-466.
• Keating J.P., Quantum graphs and quantum chaos, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 279–290.
• Kigami J., “Analysis on fractals”, Cambridge Tracts in Mathematics 143, Cambridge University Press, 2001.
• Kotani M., Sunada T., Albanese maps and off diagonal long time asymptotics for the heat kernel, Comm. Math. Phys., 209 (2000) 633–670.
• Kotani M., Sunada T., Spectral geometry of crystal lattices, in: “Heat kernels and analysis on manifolds, graphs, and metric spaces”, Contem. Math. 338, AMS, Providence, RI, 2003. 271–305.
• Kumagai T., Heat kernel estimates and parabolic Harnack inequalities on graphs and resistance forms, Publ. RIMS, Kyoto Univ., 40 (2004) 793–818.
• Lawler G.F., Sokal A.D., Bounds on the $L^2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality, Trans. Amer. Math. Soc, 309 (1988) 557–580.
• Lee J.R., Oveis Gharan S., Trevisan L., Multi-way spectral partitioning and higher-order Cheeger inequalities, in: “STOC12 Proceedings of the 2012 ACM Symposium on Theory of Computing”, ACM, New York, 2012. 1117–1130.
• Lee S.-L., Luo Y.-L., Yeh Y.-N., Topological analysis of some special graphs: III. Regular polyhedra, J. Cluster Science, 2 (1991) 219–229.
• Lenz D., Teplyaev A., Expansion in generalized eigenfunctions for Laplacians on graphs and metric measure spaces, Trans. Amer. Math. Soc., 368 (2016) 4933–4956.
• Lin Y., Lu L., Yau S.-T., Ricci curvature of graphs, Tohoku Math. J., 63 (2011) 605–627.
• Lin Y., Lu L., Yau S.-T., Ricci-flat graphs with girth at least five, Comm. Anal. Geom., 22 (2014) 671–687.
• Lin Y., Yau S.-T., Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett., 17 (2010) 343–356.
• Liu S., Multi-way dual Cheeger constants and spectral bounds of graphs, Adv. Math., 268 (2015) 306–338.
• Lovász L., Simonovits M., The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, in: “Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990)”, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990. 346–354.
• Lubotzky A., “Discrete groups, expanding graphs and invariant measures”, Progr. Math., 125, Birkhäuser Verlag, Basel, 1994.
• Lust-Piquard F., Lower bounds on $\left \Vert {K^n} \right \Vert _{1\to \infty }$ for some contractions $K$ of $L^2(\mu ),$ with some applications to Markov operators, Math. Ann., 303 (1995) 699-712.
• Mohar B., Woess W., A survey on spectra of infinite graphs, Bull. London Math. Soc., 21 (198) 209–234.
• Nash-Williams C. St. J. A., Random walks and electric current in networks, Proc. Cambridge Phil. Soc., 55 (1959) 181-194.
• Pang M.M.H., Heat kernels on graphs, J. London Math. Soc. (2), 47 (1993) 50–64.
• Pittet Ch., Følner sequences on polycyclic groups, Rev. Mat. Iberoam., 11 (1995) 675-686.
• Pittet Ch., Saloff-Coste L., Amenable groups, isoperimetric profiles and random walks, in: “Geometric group theory down under. Proceedings of a special year in geometric group theory, Canberra, Australia, 1996”, Walter De Gruyter, Berlin, 1999. 293–316.
• Pittet Ch., Saloff-Coste L., On the stability of the behavior of random walks on groups, J. Geom. Anal., 10 (2000) 713-737.
• Pittet Ch., Saloff-Coste L., On random walks on wreath products, Ann. Prob, 30 (2002) 948–977.
• Pittet Ch., Saloff-Coste L., Random walks on abelian-by-cyclic groups, Proc. Amer. Math. Soc., 131 (2003) 1071–1079.
• Rahman Md.S., “Basic graph theory”, Undergraduate Topics in Computer Science, Springer, Cham, 2017.
• Rigo M., “Advanced graph theory and combinatorics”, Computer Engineering Series, ISTE, London; John Wiley and Sons, Inc., Hoboken, NJ, 2016.
• Saloff-Coste L., Lectures on finite Markov chains, in: “Lectures on probability theory and statistics”, Lecture Notes Math. 1665, Springer, 1997. 301-413.
• Schenker J., Aizenman M., The creation of spectral gaps by graph decoration, Lett. Math. Phys., 53 (2000) 253–262.
• Shubin M., Sunada T., Geometric theory of lattice vibrations and specific heat, arXiv:math-ph/051288
• Soardi P.M., “Potential theory on infinite networks”, Lecture Notes in Mathematics 1590, Springer, 1994.
• Strichartz R.S., “Differential equations on fractals. A tutorial”, Princeton University Press, Princeton, NJ, 2006.
• Sunada T., Discrete geometric analysis, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 51–83.
• Sunada, T, Topological crystallography. With a view towards discrete geometric analysis, Surveys and Tutorials in the Applied Mathematical Sciences 6, Springer, Tokyo, 2013.
• Telcs A., “The art of random walks”, Lecture Notes in Mathematics 1885, Springer, 2006.
• Terras A., Survey of spectra of Laplacians on finite symmetric spaces, Experiment Math, 5 (1996) 15–32.
• Terras A., “Fourier analysis on finite groups and applications”, Cambridge Univ. Press, 1999.
• Terras A., A survey of discrete trace formulas, IMP Vol. Math. and Appl., 109 (1999) 643–681.
• Varopoulos N.Th., Random walks on soluble groups, Bull. Sci. Math., 107 (1983) 337-344.
• Varopoulos N.Th., Long range estimates for Markov chains, Bull. Sci. Math., 109 (1985) 113-119.
• Varopoulos N.Th., Saloff-Coste L., Coulhon T., “Analysis and geometry on groups”, Cambridge Tracts in Mathematics 100, Cambridge University Press, 1992.
• Wang F.-Y., Criteria of spectral gap for Markov operators, J. Funct. Anal., 266 (2014) 2137–2152.
• Woess W., “Random walks on infinite graphs and groups”, Cambridge Tracts in Mathematics 138, Cambridge Univ. Press., 2000.

• Alexopoulos G.K., A lower estimate for central probabilities on polycyclic groups, Can. J. Math., 44 (1992) 897-910.
• Alon N., Milman V.D., $\lambda _1$ isoperimetric inequalities for graphs and superconcentrators, J. Comb. Theory B, 38 (1985) 73-88.
• Auscher P., Coulhon T., Grigor’yan A., ed., “Heat kernels and analysis on manifolds, graphs, and metric spaces”, Contem. Math. 338, AMS, Providence, RI, 2003.
• Babson E., Barcelo H., de Longueville M., Laubenbacher R., Homotopy theory of graphs, J. Algebr. Comb., 24 (2006) 31–44.
• Bachoc C., DeCorte E., de Oliveira Filho F.M., Vallentin F., Spectral bounds for the independence ratio and the chromatic number of an operator, Israel J. Math, 202 (2014) 227–254.
• Band R., Oren I., Smilansky U., Nodal domains on graphs - how to count them and why?, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 5–27.
• Barcelo H., Capraro V., White J.A., Discrete homology theory for metric spaces, Bull. London Math. Soc., 46 (2014) 889–905.
• Barlow M.T., Diffusions on fractals, in: “Lectures on Probability Theory and Statistics, Ecole d’été de Probabilités de Saint-Flour XXV - 1995”, Lecture Notes Math. 1690, Springer, 1998. 1-121.
• Barlow M.T., Which values of the volume growth and escape time exponent are possible for graphs?, Rev. Mat. Iberoam., 40 (2004) 1-31.
• Barlow M.T., “Random walks and heat kernels on graphs”, LMS Lecture Note Series 438, Cambridge Univ. Press, 2017.
• Barlow M.T., Bass R.F., Stability of parabolic Harnack inequalites, Trans. Amer. Math. Soc., 356 (2004) 1501–1533.
• Barlow M.T., Bass R.F., Kumagai T., Parabolic Harnack inequality and heat kernel estimates for random walks with long range jumps, Math. Z., 261 (2009) 297-320.
• Barlow M.T., Coulhon T., Grigor’yan A., Manifolds and graphs with slow heat kernel decay, Invent. Math., 144 (2001) 609-649.
• Barlow M.T., Coulhon T., Kumagai T., Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs, Comm. Pure Appl. Math., 58 (2005) 1642–1677.
• Barlow M.T., Perkins E.A., Symmetric Markov chains in $\Bbb {Z}^d$: how fast can they move?, Probab. Th. Rel. Fields, 82 (1989) 95–108.
• Bartholdi L., Grigorchuk R., Spectra of non-commutative dynamical systems and graphs related to fractal groups, C. R. Acad. Sci. Paris Ser. I Math. 331 (2000) 429–434.
• Bartholdi L., Grigorchuk R., Nekrashevych V., From fractal groups to fractal sets, in: “Fractals in Graz 2001”, Trends Math., Birkhäuser, Basel, 2003. 25–119.
• Bass H., The degree of polynomial growth of finitely generated groups, Proc. London Math. Soc., 25 (1972) 603–614.
• Bass H., The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math., 3 (1992) 717–797.
• Bauer F., Horn P., Lin Y., Lippner G., Mangoubi D., Yau S.-T., Li-Yau inequality on graphs, J. Diff. Geom., 99 (2015) 359–405.
• Bauer F., Hua B., Jost J., The dual Cheeger constant and spectra of infinite graphs, Adv. Math., 251 (2014) 147–194.
• Bauer F., Jost J., Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator, Comm. Anal. Geom., 21 (2013) 787–845.
• Bauer F., Jost J., Liu S., Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, Math. Res. Lett., 19 (2012) 1185–1205.
• von Below J., Can one hear the shape of a network?, in: “Partial differential equations on multistructures (Lumini 1999)”, Lecture Notes in Pure and Appl. Math. 219, Dekker, New York, 2001. 19–36.
• Bendikov A., Grigor’yan A., Pittet Ch., Woess W., Isotropic Markov semigroups on ultra-metric spaces, Russian Math. Surveys, 69 (2014) 589–680.
• Berkolaiko G., Carlson R., Fulling S., Kuchment P. ed., “Quantum graphs and their applications”, Contemp. Math. 415, AMS, Providence, RI, 2006.
• Berkolaiko G., Kuchment P., “Introduction to quantum graphs”, Mathematical Surveys and Monographs 186, AMS, Providence, RI, 2013.
• Berkolaiko G., A lower bound for nodal count on discrete and metric graphs, to appear in Commun. Math. Phys.
• Biggs N., “Algebraic graph theory”, Cambridge Univ. Press, 2001.
• Bıyıkoğlu T., Leydold J., Stadler P.F., “Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems”, Lecture Notes in Mathematics 1915, Springer, 2007.
• Bollobás, B., “Modern graph theory”, Graduate Texts in Mathematics 184, Springer, 1998.
• Carne K., A transmutation formula for Markov chains, Bull. Sci. Math., 109 (1985) 399-403.
• Cheng S.Y., Yau S.-T., Differential equations on Riemannian manifolds and their geometric applications, Comm. Pure Appl. Math., 28 (1975) 333-354.
• Chung F.R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2 (1989) 187-196.
• Chung F.R.K., “Spectral Graph Theory”, CBMS Regional Conference Series in Mathematics 92, AMS, Providence, RI, 1997.
• Chung F.R.K., Discrete isoperimetric inequalities, in: “Eigenvalues of Laplacians and other geometric operators”, Surveys in Differential Geometry IX, (2004) 53-82.
• Chung F.R.K., Faber V., Manteuffel Th. A., An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian, SIAM J. of Discrete Math., 7 (1994) 443–457.
• Chung F.R.K., Graham R., “Erdös on graphs. His legacy of unsolved problems”, A K Peters, Ltd., Wellesley, MA, 1998.
• Chung F.R.K., Grigor’yan A., Yau S.-T., Upper bounds for eigenvalues of the discrete and continuous Laplace operators, Advances in Math., 117 (1996) 165-178.
• Chung F.R.K., Grigor’yan A., Yau S.-T., Eigenvalues and diameters for manifolds and graphs, in: “Tsinghua Lectures on Geometry and Analysis”, International Press, 1997. 79-105.
• Chung F.R.K., Lin Y., Yau S.-T., Harnack inequalities for graphs with non-negative Ricci curvature, J. Math. Anal. Appl, 415 (2014) 25–32.
• Chung F.R.K., Lu L., “Complex Graphs and Networks”, CBMS Regional Conference Series in Mathematics 107, AMS, Providence, RI, 2006.
• Chung F.R.K., Yau S.-T., Eigenvalue inequalities for graphs and convex subgraphs, Comm. in Analysis and Geom., 2 (1994) 628-639.
• Chung F.R.K., Yau, S.-T., Eigenvalues of graphs and Sobolev inequalities, Combinatorics, Probability and Computing, 4 (1995) 11-26.
• Colin de Verdière Y., “Spectres de graphes”, Cours Spécialisés 4, Société Mathématique de France, Paris, 1998.
• Coulhon T., Sobolev inequalities on graphs and manifolds, in: “Harmonic Analysis and Discrete Potential Theory”, Plenum Press, New York and London, 1992.
• Coulhon T., Grigor’yan A., On-diagonal lower bounds for heat kernels on non-compact manifolds and Markov chains, Duke Math. J., 89 (1997) 133-199.
• Coulhon T., Grigor’yan A., Random walks on graphs with regular volume growth, Geom. Funct. Anal., 8 (1998) 656-701.
• Coulhon T., Grigor’yan A., Pittet Ch., A geometric approach to on-diagonal heat kernel lower bounds on groups, Ann. Inst. Fourier, Grenoble, 51 (2001) 1763-1827.
• Coulhon T., Grigor’yan A., Zucca F., The discrete integral maximum principle and its applications, Tohoku Math. J., 57 (2005) 559-587.
• Coulhon T., Saloff-Coste L., Isopérimétrie pour les groupes et les variétés, Rev. Mat. Iberoam., 9 (1993) 293-314.
• Cvetkovic D., Doob M., Gutman I., Targasev A., “Recent results in the theory of graph spectra”, Ann. Disc. Math. 36, North Holland, 1988.
• Cvetkovic D., Doob M., Sachs H., “Spectra of graphs”, Acad. Press., NY, 1979.
• Davidoff G., Sarnak P., Valette A., “Elementary number theory, group theory and Ramanujan graphs”, Cambridge Univ. Press, 2003.
• Davies E.B., Large deviations for heat kernels on graphs, J. London Math. Soc. (2), 47 (1993) 65-72.
• Delmotte T., Parabolic Harnack inequality and estimates of Markov chains on graphs, Rev. Mat. Iberoam., 15 (1999) 181-232.
• Diaconis P., Saloff-Coste L., What do we know about the Metropolis Algorithm?, J. of Computer and System Sciences, 57 (1998) 20-36.
• Diaconis P., Stroock D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Prob., 1 (1991) 36-61.
• Diestel R., “Graph theory”, Graduate Texts in Mathematics 173, Springer, Berlin, 2017.
• Dimakis A., Müller-Hoissen F., Discrete differential calculus: graphs, topologies, and gauge theory, J. Math. Phys., 35 (1994) 6703-6735.
• Dodziuk J., Difference equations, isoperimetric inequalities and transience of certain random walks, Trans. Amer. Math. Soc., 284 (1984) 787-794.
• Dodziuk J., Kendall W.S., Combinatorial Laplacians and isoperimetric inequality, in: “From local times to global geometry, control and physics (Coventry, 1984/85)”, Pitman Res. Notes Math. Ser. 150, 1986. 68–74.
• Doyle P.G., Snell J.L., “Random walks and electric networks”, Carus Mathematical Monographs 22, Mathematical Association of America, Washington, DC, 1984.
• Exner P., Keating J.P., Kuchment P., Sunada T., Teplyaev A., ed., “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008.
• Figa-Talamanca A., “Harmonic analysis on free groups”, CRC, 1983.
• Figa-Talamanca A., Nebbia C., “Harmonic analysis and representation theory for groups acting on homogenous trees”, Cambridge Univ. Press, 1991.
• Friedlander L., Genericity of simple eigenvalues for a metric graph, Israel J. Math., 146 (2005) 149–156.
• Gaveau B., Okada M., Differential forms and heat diffusion on one-dimensional singular varieties, Bull. Sci. Math., 115 (1991) 61–80.
• Gaveau B., Okada M., Okada T., Explicit heat kernels on graphs and spectral analysis, in: “Several complex variables (Proceedings of the Mittag-Leffler Institute, Stockholm, 1987-88)”, Princeton Math. Notes 38, Princeton University Press, 1993. 364–388.
• Gieseker D., Knörrer H., Trubowitz E., “The geometry of algebraic Fermi curves”, Academic Press, Boston, 1992.
• Godsil C., Royle G., “Algebraic graph theory”, Graduate Texts in Mathematics 207, Springer, New York, 2001.
• Grigor’yan A., On the existence of positive fundamental solution of the Laplace equation on Riemannian manifolds, (in Russian) Matem. Sbornik, 128 (1985) 354-363. Engl. transl.: Math. USSR Sb., 56 (1987) 349-358.
• Grigor’yan A., Heat kernels on metric measure spaces, in: “Handbook of Geometric Analysis Vol. 2”, Ed. L. Ji, P. Li, R. Schoen, L. Simon, Advanced Lectures in Math. 13, International Press, 2010. 1-60.
• Grigor’yan A., Kelbert M., On Hardy-Littlewood inequality for Brownian motion on Riemannian manifolds, J. London Math. Soc. (2), 62 (2000) 625-639.
• Grigor’yan A., Lin Y., Muranov Yu., Yau S.-T., Homotopy theory for digraphs, Pure Appl. Math. Quaterly, 10 (2014) 619-674.
• Grigor’yan A., Lin Y., Muranov Yu., Yau S.-T., Path complexes and their homologies, to appear in Int. J. Math.
• Grigor’yan A., Muranov Yu., Yau S.-T., Graphs associated with simplicial complexes, Homology, Homotopy and Appl., 16 (2014) 295–311.
• Grigor’yan A., Muranov Yu., Yau S.-T., Cohomology of digraphs and (undirected) graphs, Asian J. Math., 19 (2015) 887-932.
• Grigor’yan A., Muranov Yu., Yau S.-T., On a cohomology of digraphs and Hochschild cohomology, J. Homotopy Relat. Struct., 11 (2016) 209–230.
• Grigor’yan A., Muranov Yu., Yau S.-T., Homologies of digraphs and Künneth formulas, Comm. Anal. Geom., 25 (2017) 969–1018.
• Grigor’yan A., Telcs A., Sub-Gaussian estimates of heat kernels on infinite graphs, Duke Math. J., 109 (2001) 451-510.
• Grigor’yan A., Telcs A., Harnack inequalities and sub-Gaussian estimates for random walks, Math. Ann., 324 (2002) 521-556.
• Grigorchuk R., Nekrashevych V., Self-similar groups, operator algebras and Schur complement, J. Modern Dynamics, 1 (2007) 323–370.
• Grigorchuk R., Sunik Z., Asymptotic aspects of Schreier graphs and Hanoi towers groups, C. R. Acad. Sci. Paris Ser. I Math. 342 (2006) 545–550.
• Grigorchuk R., Zuk A., The Ihara zeta function of infinite graphs, the KNS spectral measure and integrable maps, in: “Random walks and geometry”, Walter de Gruyter, Berlin, 2004. 141–180.
• Grimmet J., “Probability on graphs: random Processes on graphs and lattices, 2nd edition”, Cambridge Univ. Press, 2017.
• Hambly B.M., Kumagai T., Heat kernel estimates and law of the iterated logarithm for symmetric random walks on fractal graphs, in: “Discrete geometric analysis”, Contemp. Math. 347, Amer. Math. Soc., Providence, RI, 2004. 153–172.
• Hambly B.M., Kumagai T., Heat kernel estimates for symmetric random walks on a class of fractal graphs and stability under rough isometries, in: “Fractal geometry and applications: a jubilee of Benoît Mandelbrot, Part 2” Proc. Sympos. Pure Math. 72 Part 2, Amer. Math. Soc., Providence, RI, 2004. 233–259.
• Hebisch W., Saloff-Coste, L., Gaussian estimates for Markov chains and random walks on groups, Ann. Prob., 21 (1993) 673–709.
• Higuchi Y., Nomura Y., Spectral structure of the Laplacian on a covering graph, European J. Combin., 30 (2009) 570–585.
• Hoffman A.J., On eigenvalues and colorings of graphs, in: “Graph Theory and its Applications”, Academic Press, New York, 1970. 79–91.
• Horton M.D., Stark H.M., Terras A.A., What are zeta functions of graphs and what are they good for?, in: “Quantum graphs and their applications”, Contemp. Math. 415, AMS, Providence, RI, 2006. 173–189.
• Horton M.D., Stark H.M., Terras A.A., Zeta functions of weighted and covering graphs, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 29–50.
• Hua B., Lin Y., Curvature notions on graphs, Front. Math. China, 11 (2016) 1275–1290.
• Hua B., Lin Y., Stochastic completeness for graphs with curvature dimension conditions, Adv. Math., 306 (2017) 279–302.
• Kaimanovich V.A., Vershik A.M., Random walks on discrete groups: boundary and entropy, Ann. Prob., 11 (1983) 457-490.
• Kaimanovich V.A., Woess W., The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality, Probab. Th. Rel. Fields, 91 (1992) 445-466.
• Keating J.P., Quantum graphs and quantum chaos, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 279–290.
• Kigami J., “Analysis on fractals”, Cambridge Tracts in Mathematics 143, Cambridge University Press, 2001.
• Kotani M., Sunada T., Albanese maps and off diagonal long time asymptotics for the heat kernel, Comm. Math. Phys., 209 (2000) 633–670.
• Kotani M., Sunada T., Spectral geometry of crystal lattices, in: “Heat kernels and analysis on manifolds, graphs, and metric spaces”, Contem. Math. 338, AMS, Providence, RI, 2003. 271–305.
• Kumagai T., Heat kernel estimates and parabolic Harnack inequalities on graphs and resistance forms, Publ. RIMS, Kyoto Univ., 40 (2004) 793–818.
• Lawler G.F., Sokal A.D., Bounds on the $L^2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality, Trans. Amer. Math. Soc, 309 (1988) 557–580.
• Lee J.R., Oveis Gharan S., Trevisan L., Multi-way spectral partitioning and higher-order Cheeger inequalities, in: “STOC12 Proceedings of the 2012 ACM Symposium on Theory of Computing”, ACM, New York, 2012. 1117–1130.
• Lee S.-L., Luo Y.-L., Yeh Y.-N., Topological analysis of some special graphs: III. Regular polyhedra, J. Cluster Science, 2 (1991) 219–229.
• Lenz D., Teplyaev A., Expansion in generalized eigenfunctions for Laplacians on graphs and metric measure spaces, Trans. Amer. Math. Soc., 368 (2016) 4933–4956.
• Lin Y., Lu L., Yau S.-T., Ricci curvature of graphs, Tohoku Math. J., 63 (2011) 605–627.
• Lin Y., Lu L., Yau S.-T., Ricci-flat graphs with girth at least five, Comm. Anal. Geom., 22 (2014) 671–687.
• Lin Y., Yau S.-T., Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett., 17 (2010) 343–356.
• Liu S., Multi-way dual Cheeger constants and spectral bounds of graphs, Adv. Math., 268 (2015) 306–338.
• Lovász L., Simonovits M., The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, in: “Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990)”, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990. 346–354.
• Lubotzky A., “Discrete groups, expanding graphs and invariant measures”, Progr. Math., 125, Birkhäuser Verlag, Basel, 1994.
• Lust-Piquard F., Lower bounds on $\left \Vert {K^n} \right \Vert _{1\to \infty }$ for some contractions $K$ of $L^2(\mu ),$ with some applications to Markov operators, Math. Ann., 303 (1995) 699-712.
• Mohar B., Woess W., A survey on spectra of infinite graphs, Bull. London Math. Soc., 21 (198) 209–234.
• Nash-Williams C. St. J. A., Random walks and electric current in networks, Proc. Cambridge Phil. Soc., 55 (1959) 181-194.
• Pang M.M.H., Heat kernels on graphs, J. London Math. Soc. (2), 47 (1993) 50–64.
• Pittet Ch., Følner sequences on polycyclic groups, Rev. Mat. Iberoam., 11 (1995) 675-686.
• Pittet Ch., Saloff-Coste L., Amenable groups, isoperimetric profiles and random walks, in: “Geometric group theory down under. Proceedings of a special year in geometric group theory, Canberra, Australia, 1996”, Walter De Gruyter, Berlin, 1999. 293–316.
• Pittet Ch., Saloff-Coste L., On the stability of the behavior of random walks on groups, J. Geom. Anal., 10 (2000) 713-737.
• Pittet Ch., Saloff-Coste L., On random walks on wreath products, Ann. Prob, 30 (2002) 948–977.
• Pittet Ch., Saloff-Coste L., Random walks on abelian-by-cyclic groups, Proc. Amer. Math. Soc., 131 (2003) 1071–1079.
• Rahman Md.S., “Basic graph theory”, Undergraduate Topics in Computer Science, Springer, Cham, 2017.
• Rigo M., “Advanced graph theory and combinatorics”, Computer Engineering Series, ISTE, London; John Wiley and Sons, Inc., Hoboken, NJ, 2016.
• Saloff-Coste L., Lectures on finite Markov chains, in: “Lectures on probability theory and statistics”, Lecture Notes Math. 1665, Springer, 1997. 301-413.
• Schenker J., Aizenman M., The creation of spectral gaps by graph decoration, Lett. Math. Phys., 53 (2000) 253–262.
• Shubin M., Sunada T., Geometric theory of lattice vibrations and specific heat, arXiv:math-ph/051288
• Soardi P.M., “Potential theory on infinite networks”, Lecture Notes in Mathematics 1590, Springer, 1994.
• Strichartz R.S., “Differential equations on fractals. A tutorial”, Princeton University Press, Princeton, NJ, 2006.
• Sunada T., Discrete geometric analysis, in: “Analysis on graphs and its applications”, Proc. Sympos. Pure Math. 77, AMS, Providence, RI, 2008. 51–83.
• Sunada, T, Topological crystallography. With a view towards discrete geometric analysis, Surveys and Tutorials in the Applied Mathematical Sciences 6, Springer, Tokyo, 2013.
• Telcs A., “The art of random walks”, Lecture Notes in Mathematics 1885, Springer, 2006.
• Terras A., Survey of spectra of Laplacians on finite symmetric spaces, Experiment Math, 5 (1996) 15–32.
• Terras A., “Fourier analysis on finite groups and applications”, Cambridge Univ. Press, 1999.
• Terras A., A survey of discrete trace formulas, IMP Vol. Math. and Appl., 109 (1999) 643–681.
• Varopoulos N.Th., Random walks on soluble groups, Bull. Sci. Math., 107 (1983) 337-344.
• Varopoulos N.Th., Long range estimates for Markov chains, Bull. Sci. Math., 109 (1985) 113-119.
• Varopoulos N.Th., Saloff-Coste L., Coulhon T., “Analysis and geometry on groups”, Cambridge Tracts in Mathematics 100, Cambridge University Press, 1992.
• Wang F.-Y., Criteria of spectral gap for Markov operators, J. Funct. Anal., 266 (2014) 2137–2152.
• Woess W., “Random walks on infinite graphs and groups”, Cambridge Tracts in Mathematics 138, Cambridge Univ. Press., 2000.