Skip to content

Spectra and geometric invariants of graphs, networks, and polygonal complexes (Norbert Peyerimhoff)

Graphs, networks, and polygonal complexes are discrete geometric spaces appearing in countless theoretical contexts and applications (concrete practical examples are the World Wide Web, the Power Grid or social networks, but also polygon meshes in geometric modeling and 3D computer graphics). It is natural to introduce and to study local and global quantitative invariants for these discrete objects with the aim to measure their differences, to find strongly connected components, to construct and to work with good embeddings into Euclidean and non-Euclidean spaces, and to better understand their topology and other important properties. We are particularly interested in the following invariants and their relations:

  • eigenvalues and eigenvectors of associated adjacency matrices (global spectral invariants)
  • vertex and edge expansion rates, Cheeger constants (global isoperimetric invariants)
  • synthetic curvatures (local geometric invariants)
  • fundamental and cohomology groups (global topological invariants)

The beauty in this topic is that important discoveries can already be made without too much background knowledge while — at the same time — there are strong and deep connections to various areas of theoretical mathematics like combinatorial and geometric group theory, number theory (e.g., Ramanujan graphs), probability and analysis (e.g., random walks and heat kernels), dynamics, discrete and hyperbolic geometry, and the topic has also various practical applications like spectral clustering (e.g., robust communication networks), visualisation (e.g., triangulations of surfaces), and in coding theory and complexity theory.

PhD projects in this area can be supervised jointly with D. Cushing (spectral invariants and synthetic curvatures), A. Vdovina (spectral and topological invariants, geometric group theory), or I. Ivrissimtzis (spectral invariants, triangulations, and applications to visualisation).


Graph appearing in a special family of 4-regular expander graphs,
forming a tower of coverings (see [PV] below)


The antitree is an infinite graph with strictly positive (Bakry-Emery) curvature; Illustration via an applet by G. Stagg and D. Cushing (related to [LMP] below)


 

Some articles

  • [CLP] D. Cushing, Sh. Liu, N. Peyerimhoff: Bakry-Émery curvature functions of graphs, arXiv:1606.01496 (June 2016)
  • [HLW] Sh. Hoory, N. Linial, A. Wigderson: Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006)
  • [IP] I. Ivrissimtzis, N. Peyerimhoff: Spectral representations of vertex transitive graphs, Archimedean solids and finite Coxeter groups, Groups Geom. Dyn. 7 (2013)
  • [KPP] M. Keller, N. Peyerimhoff, F. Pogorzelski: Sectional curvature of polygonal complexes with planar substructures, Adv. Math. 307 (2017)
  • [LMP] Sh. Liu, F. Münch, N. Peyerimhoff: Bakry-Emery curvature and diameter bounds on graphs, arXiv:1608.07778 (November 2016)
  • [M] M. Ram Murty: Ramanujan graphs, J. Ramanujan Math. Soc. 18 (2003)
  • [PV] N. Peyerimhoff, A. Vdovina: Cayley graph expanders and groups of finite width, J. Pure Appl. Algebra 215 (2011)
  • [vL] U. von Luxburg: A tutorial on spectral clustering, Stat. Comput. 17 (2007)