We show that random walk on a stationary random graph with positive anchored expansion and exponential volume growth has positive speed. We also show that two families of random triangulations of the hyperbolic plane, the hyperbolic Poisson Voronoi tessellation and the hyperbolic Poisson Delaunay triangulation, have 1-skeletons with positive anchored expansion. As a consequence, we show that the simple random walks on these graphs have positive speed. We include a section of open problems and conjectures on the topics of stationary geometric random graphs and the hyperbolic Poisson Voronoi tessellation. [-]

A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure.[-]

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.[-]

The space of subgroups of a countable group G is a compact Polish space equipped with a natural G-action. It is the crucible where certain properties of the non-free actions of G boil down, whether they are of a topological or measured nature. We will discuss several approaches to determining the Cantor-Bendixson decomposition of this space. In particular, we find the perfect kernel and the Cantor Bendixson rank of the subgroup space of many new groups, including infinitely ended groups, limit groups and hyperbolic 3manifold groups. We also give conditions under which the action on the perfect kernel is topologically transitive. This is joint work with Damien Gaboriau.[-]

We consider a special family of invariant random processes on the infinite d-regular tree, which is closely related to random d-regular graphs, and helps understanding the structure of these finite objects. By using different notions of entropy and finding inequalities between these quantities, we present a sufficient condition for a process to be typical, that is, to be the weak local limit of functions on the vertices of a randomly chosen d-regular graph (with fixed d, and the number of vertices tending to infinity). Our results are based on invariant couplings of the process with another copy of itself. The arguments can also be extended to processes on unimodular Galton-Watson trees. In the talk we present the notion of typicality, the entropy inequalities that we use and the sufficient conditions mentioned above. Joint work with Charles Bordenave and Balázs Szegedy.[-]

We show that several new classes of groups are measure strongly treeable, i.e., all of their free measure-class-preserving actions are treeable. This includes all finitely generated groups admitting planar Cayley graphs, all finitely generated elementarily free groups, and more generally all groups arising as the fundamental group of an 'IFL tower' over these groups. Our techniques also lead to new measure strong free factors of groups, i.e., group elements which generate a primitive subrelation in every free measure-class-preserving action. This is based on joint work with Clinton Conley, Damien Gaboriau, and Andrew Marks.[-]

We consider the class of finitely generated groups admitting a nonelementary and cocompact action on a locally finite tree, with vertex stabilizers virtually free abelian of rank $n \geq 1$. In the case $n=1$, Baumslag-Solitar groups are examples of such groups. The behavior of that class of groups with respect to quasi-isometries is described by works of Mosher-Sageev-Whyte, Farb-Mosher, and Whyte.
We study the commability rigidity problem for this class of groups. Such a group $\Gamma$ admits a canonical linear representation $ \rho_\Gamma$ over an $n$-dimensional $Q$-vector space. Our main result provides a necessary criterion for two groups $\Gamma,\Lambda$ to be commable, in terms of the images of the representations $ \rho_\Gamma$ and $\rho_\Lambda$. This result complements Whyte's quasi-isometric classification within this class of groups, and it implies that many groups in this class are not commable, although they are quasi-isometric. Joint work with Yves Cornulier.[-]