Groups, Graphs and Stochastic Processes (15w5146)

Arriving in Banff, Alberta Sunday, June 21 and departing Friday June 26, 2015


(Alfred Renyi Institute of Mathematics)

(University of British Columbia)

Balint Virag (University of Toronto)


The proposed workshop aims to bring together experts and young researchers in the following fields: asymptotic group theory, ergodic theory, $L^{2}$ invariants, geometric group theory, percolation, random walks, 3-manifold theory, statistical physics and algebraic graph theory. The common object of interest to all these is graph convergence and unimodular random graphs (in the language of probability), measure preserving actions of a countable group (in the language of group theory), and graphings (in the language of graph theory) as well as processes on these structures. Each field investigates this object from a different angle, and although there is already considerable interaction, more would definitely be productive.

The proposed workshop is a continuation of the workshop with the same title, held in June 2011 at BIRS, Banff. That workshop was quite successful and there is a definite need in the community for a follow-up. We list here some recent examples where ideas from one of the subjects listed above were applied in a ground-breaking way in another. Note that some of these, like Bowen's work on invariant random subgroups, started from conversations at the last workshop in Banff.

• Luck approximation and the theory of groups with positive mod p homology growth by Osin, Ershov and Jaikin-Zapirain and the new framework of using sofic entropy for understanding the mod p homology growth by Abert and Szegedy;

• Kesten's theorem on invariant random subgroups and unimodular random graphs by Abert, Glasner and Virag, and the new result of Lyons and Peres on infinite Ramanujan graphs;

• The Bowen-Kerr-Li sofic entropy and the new sofic entropy notion by Abert and Weiss. These theories build an entropy theory for actions of non-amenable groups, using sofic approximations. A new direction here is for non-free actions, using invariant random subgroups.

• The Bayati-Gamarnik-Tetali result, proving that the independence ratio converges for sequences of random regular graphs, Gamarnik and Sudan's result on showing that in regular random graphs, maximal independent sets can not be obtained by local algorithms.

• Lee, Gharan and Trevisan's generalization of Cheeger's inequality for graphs: there are $k$ eigenvalues close to zero if and only if the vertex set can be partitioned into $k$ subsets, each defining a sparse cut;

• The Gaboriau-Lyons solution of the measurable version of von Neumann's problem using percolation on transitive graphs and its analogue for finite expander graphs by Kun and the measurable Local Lemma;

• Using invariant random subgroups and Benjamini-Schramm convergence for locally symmetric spaces, by Abert, Bergeron, Biringer, Gelander, Nikolov, Raimbault and Samet, the work of Bowen on invariant random subgroups;

• Abert and Nikolov's work on profinite actions connecting the fixed price problem to the ``rank vs. Heegaard genus problem'' in 3-manifold theory and the recent work of Abert and Gaboriau on higher dimensional analogues of cost and the growth of deficiency;

• Gaboriau's work on distinguishing ergodic equivalence relations by developing a measure-theoretic analogue of $L^{2}$ Betti numbers;

• The work of Keller on the absolutely continuous spectrum of some Galton-Watson trees. The work on Bordenave, Sen and Virag on the continuous part of the expected spectral measure on Galton-Watson trees and percolation clusters;

• The work of Marcus, Spielman, Srivastava on the proof of the Bilu-Lineal conjecture and the new families of bipartite Ramanujan graphs;

• The work of Angel and Szegedy of extending the Benjamini-Schramm theorem on planar graphs to minor-closed families.

Much more is expected to happen. We hope that the meeting will lead to a new understanding of the already existing directions and will further pave the way to building a general theory. The suggested participant list consists of people who, while being top experts in their own fields of research, are also willing to think outside the box and assimilate each others' points of view.