Ágnes Backhausz
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.