We study connections between distributed local algorithms, finitary factors of iid processes,
and descriptive combinatorics in the context of regular trees. We extend the Borel …

We present an intimate connection among the following fields:(a) distributed local
algorithms: coming from the area of computer science,(b) finitary factors of iid processes …

In this article we survey the emerging field of descriptive graph combinatorics. This area has
developed in the last two decades or so at the interface of descriptive set theory and graph …

A Borel graph on a standard Borel space X is a symmetric irreflexive relation G on X that is
Borel as a subset of X× X. We call elements of X vertices, and if x, y∈ X and xGy, then we …

In this paper we consider coloring problems on graphs and other combinatorial structures on
standard Borel spaces. Our goal is to obtain sufficient conditions under which such colorings …

Let d\geq3 be fixed and G be a large random d-regular graph on n vertices. We show that if
n is large enough then the entry distribution of every almost eigenvector of G (with entry sum …

We establish two versions of Vizing's theorem for Borel multi-graphs whose vertex degrees
and edge multiplicities are uniformly bounded by respectively Δ and π. The “approximate” …

We introduce new types of examples of bounded degree acyclic Borel graphs and study
their combinatorial properties in the context of descriptive combinatorics, using a …

In this paper we investigate the extent to which the Lovász Local Lemma (an important tool
in probabilistic combinatorics) can be adapted for the measurable setting. In most …

Asymptotic separation index is a parameter that measures how easily a Borel graph can be
approximated by its subgraphs with finite components. In contrast to the more classical …