Ágnes Backhausz

Rényi Institute

Ramanujan graphings and randomized local algorithms

We examine randomized local algorithms on d-regular graphs that do not contain short cycles (which are strongly related to factor of i.i.d. processes on the d-regular tree). First we assign independent and identically distributed random variables to the vertices of the graph; this is a random labelling. Then every vertex gets a new random variable, depending on its labelled neighbourhood; the rule of this decision is deterministic and it is the same for all vertices.

In the talk we present some applications of these algoritms, and their connection to graphings, which are limit objects of bounded degree graph sequences. We describe (up to closure) the possible correlation structure of these processes, and show how spectral theory of graphings can be used to prove these kind of results.

This is joint work with Balázs Szegedy and Bálint Virág.