Mar 30, 2019

Preview: Medallion lecturer, Charles Bordenave

Charles Bordenave

Charles Bordenave studied at Ecole Polytechnique in France, and received his PhD in 2006 under the supervision of François Baccelli. He was a postdoc at UC Berkeley before joining University of Toulouse as a CNRS researcher. Since 2018, he has been CNRS researcher at Aix-Marseille University. His research interests are in random matrices, random graphs, combinatorial optimization, stochastic geometry and more recently mixing times of Markov chains. He serves on the editorial boards of the Annals of Applied Probability, Annals of Probability and Bernoulli. He is the recipient of the 2017 Marc Yor prize from the French Academy of Sciences.

Charles Bordenave’s Medallion Lecture will be given at the INFORMS-APS 2019 meeting, July 3–5, 2019, in Brisbane, Australia [note that these are the correct dates, not July 2–4 as previously advertised]. The meeting website is http://informs-aps.smp.uq.edu.au/

Non-backtracking spectrum of random matrices.

A fruitful line of thought in the study of discrete combinatorial structures, such as graphs, is to look for natural matrices or operators whose spectrum will contain valuable and accessible information on the underlying combinatorial structure.

The adjacency matrix of a graph is the matrix acting on the vertices of the graph whose entries are zero or one depending on the presence or absence of an edge between a given pair of vertices. The entries of powers of the adjacency matrix count paths along the edges of the graph.

The non-backtracking matrix of a graph is a matrix acting on pairs of vertices sharing an edge. The entries of powers of the non-backtracking matrix count non-backtracking paths along the edges of the graph, that is, paths which do not successively visit the same edge twice. A non-backtracking path may be interpreted as a discrete geodesic.

This matrix was introduced by Hashimoto in 1988 in the context of the Ihara zeta function of a graph, which is an analog in a discrete setting of the Selberg zeta function of a Riemannian manifold. In recent years, due to its strong geometric flavor, this non-backtracking matrix has been promoted as a powerful tool to analyze the subtle interplay between the geometry of a graph and its spectrum.

It has found a wide range of applications. For example, in 2013, Krzakala et al. have used this matrix in the design of a spectral algorithm to detect communities in social networks which bypass some of the limitations of classical spectral algorithms. Before that, Friedman (2008) used this matrix to prove the celebrated Alon’s second eigenvalue conjecture which asserts that for any integer d, as n goes to infinity (with n×d even), almost all d-regular graphs on n vertices have the largest possible spectral gap at first order.

Non-backtracking matrices enjoy beautiful algebraic identities among which a spectral correspondence with matrices such as adjacency matrices. In this talk, we will explain how these spectral mappings can be used to translate problems on extremal eigenvalues of adjacency matrices into problems on extremal eigenvalues of weighted non-backtracking matrices.

We will then focus the talk on the study of the extremal eigenvalues of non-backtracking matrices of classical random graph ensembles: uniform regular graphs, Erdős-Rényi random graphs, stochastic block models and random n-lifts of a base graph. We will notably explain how these results can be used in community detection problems and in the theory of expander graphs, classical and quantum.

This is based on joint work with Benoit Collins, Marc Lelarge and Laurent Massoulié.

Share

Leave a comment

*

Share

Welcome!

Welcome to the IMS Bulletin website! We are developing the way we communicate news and information more effectively with members. The print Bulletin is still with us (free with IMS membership), and still available as a PDF to download, but in addition, we are placing some of the news, columns and articles on this blog site, which will allow you the opportunity to interact more. We are always keen to hear from IMS members, and encourage you to write articles and reports that other IMS members would find interesting. Contact the IMS Bulletin at bulletin@imstat.org

What is “Open Forum”?

In the Open Forum, any IMS member can propose a topic for discussion. Email your subject and an opening paragraph (to bulletin@imstat.org) and we'll post it to start off the discussion. Other readers can join in the debate by commenting on the post. Search other Open Forum posts by using the Open Forum category link below. Start a discussion today!

About IMS

The Institute of Mathematical Statistics is an international scholarly society devoted to the development and dissemination of the theory and applications of statistics and probability. We have about 4,500 members around the world. Visit IMS at http://imstat.org
Latest Issue