Search

In the past couple of years a rich connection has been found between the fields of descriptive set theory and distributed computing. Frequently, and less surprisingly, finitary algorithms can be adopted to the infinite setting, resulting in theorems about infinite, definable graphs. In this survey, we take a different perspective and illustrate how results and ideas from descriptive set theory provide new insights and techniques to the theory of distributed computing. We focus on the two classical topics from graph theory, vertex and edge colorings. After summarizing the up-to-date results from both areas, we discuss the adaptation of Marks' games method to the LOCAL model of distributed computing and the development of the multi-step Vizing's chain technique, which led to the construction of the first non-trivial distributed algorithms for Vizing colorings. We provide a list of related open problems to complement our discussion. Finally, we describe an efficient deterministic distributed algorithm for Brooks coloring on graphs of subexponential growth.

We investigate the descriptive set-theoretic complexity of the solvability of a Borel family of linear equations over a finite field. Answering a question of Thornton, we show that this problem is already hard, namely $\Sigma^1_2$-complete. This implies that the split between easy and hard problems is at a different place in the Borel setting than in the case of the CSP Dichotomy.

We investigate the behavior of countable Borel equivalence relations (CBERs) on topological Ramsey spaces. First, we give a simple proof of the fact that every CBER on $[\mathbb{N}]^{\mathbb{N}}$ is hyperfinite on some set of the form $[A]^{\mathbb{N}}$. Using the idea behind the proof, we show the analogous result for every topological Ramsey space.

We show that if there exists a countable Borel equivalence relation which is hyper-hyperfinite but not hyperfinite then the complexity of hyperfinite countable Borel equivalence relations is as high as possible, namely, $\Sigma^1_2$-complete.

We investigate the existence of FIID homomorphisms from regular trees to finite graphs. Using entropy inequalities we show that there are graphs with arbitrarily large chromatic number to which there is no FIID homomorphism from a 3-regular tree.

We study Constraint Satisfaction Problems (CSPs) in an infinite context. We show that the dichotomy between easy and hard problems -- established already in the finite case -- presents itself as the strength of the corresponding De Bruijin-Erd\H{o}s-type compactness theorem over ZF. More precisely, if $\mathcal{D}$ is a structure, let $K_\mathcal{D}$ stand for the following statement: for every structure $\mathcal{X}$ if every finite substructure of $\mathcal{X}$ admits a solution to $\mathcal{D}$, then so does $\mathcal{X}$. We prove that if $\mathcal{D}$ admits no cyclic polymorphism, and thus it is NP-complete by the CSP Dichotomy Theorem, then $K_\mathcal{D}$ is equivalent to the Boolean Prime Ideal Theorem (BPI) over ZF. Conversely, we also show that if $\mathcal{D}$ admits a cyclic polymorphism, and thus it is in P, then $K_\mathcal{D}$ is strictly weaker than BPI.

We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.

We study complexity classes of local problems on regular trees from the perspective of distributed local algorithms and descriptive combinatorics. We show that, surprisingly, some deterministic local complexity classes from the hierarchy of distributed computing exactly coincide with well studied classes of problems in descriptive combinatorics. Namely, we show that a local problem admits a continuous solution if and only if it admits a local algorithm with local complexity $O(\log^* n)$, and a Baire measurable solution if and only if it admits a local algorithm with local complexity $O(\log n)$., Comment: This paper is an extension of some parts of the conference paper "Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics (arXiv:2106.02066)

Combining canonization results of Pr\"omel-Voigt, Mathias, and Soare, we provide a new, natural example of an $F_\sigma$ equivalence relation that is not hypersmooth.

We introduce a new type of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalization of the determinacy method of Marks. The motivation for the construction comes from the adaptation of this method to the LOCAL model of distributed computing. Our approach unifies the previous results in the area, as well as produces new ones. In particular, we show that for $\Delta>2$ it is impossible to give a simple characterization of acyclic $\Delta$-regular Borel graphs with Borel chromatic number at most $\Delta$: such graphs form a $\mathbf{\Sigma}^1_2$-complete set. This implies a strong failure of Brooks'-like theorems in the Borel context.

We study topological realizations of countable Borel equivalence relations, including realizations by continuous actions of countable groups, with additional desirable properties. Some examples include minimal realizations on any perfect Polish space, realizations as $K_\sigma$ relations, and realizations by continuous actions on the Baire space. We also consider questions related to realizations of specific important equivalence relations, like Turing and arithmetical equivalence. We focus in particular on the problem of realization by continuous actions on compact spaces and more specifically subshifts. This leads to the study of properties of subshifts, including universality of minimal subshifts, and a characterization of amenability of a countable group in terms of subshifts. Moreover we consider a natural universal space for actions and equivalence relations and study the descriptive and topological properties in this universal space of various properties, like, e.g., compressibility, amenability or hyperfiniteness., Comment: 108 pages; version to be submitted

All spaces are assumed to be separable and metrizable. Ostrovsky showed that every zero-dimensional Borel space is $\sigma$-homogeneous. Inspired by this theorem, we obtain the following results: assuming $\mathsf{AD}$, every zero-dimensional space is $\sigma$-homogeneous; assuming $\mathsf{AC}$, there exists a zero-dimensional space that is not $\sigma$-homogeneous; assuming $\mathsf{V=L}$, there exists a coanalytic zero-dimensional space that is not $\sigma$-homogeneous. Along the way, we introduce two notions of hereditary rigidity, and give alternative proofs of results of van Engelen, Miller and Steel. It is an open problem whether every analytic zero-dimensional space is $\sigma$-homogeneous., Comment: 22 pages

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 determinacy technique of Marks coming from descriptive combinatorics and adapt it to the area of distributed computing. Using this technique, we prove deterministic distributed $\Omega(\log n)$-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest. We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity $O(\log n)$, extending the classification of Baire measurable colorings of Bernshteyn. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in $O(\log n)$ rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution. We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn -- arXiv 2004.04905].

Answering a question of Hru\v{s}\'ak, we show that every analytic tall ideal on $\omega$ contains an $F_\sigma$ tall ideal. We also give an example of an $F_\sigma$ tall ideal without a Borel selector.

We show that every non-Haar-null analytic subset of $\mathbb{Z}^\omega$ contains a non-Haar-null closed subset. Moreover, we also prove that the codes of Haar-null analytic subsets, and, consequently, closed Haar-null sets in the Effros Borel space of $\mathbb{Z}^\omega$ form a $\mathbf{\Delta}^1_2$ set.

We generalize Kada's definable strengthening of Dilworth's characterization of the class of quasi-orders admitting an antichain of a given finite cardinality.

We show that there is a Borel graph on a standard Borel space of Borel chromatic number three that admits a Borel homomorphism to every analytic graph on a standard Borel space of Borel chromatic number at least three. Moreover, we characterize the Borel graphs on standard Borel spaces of vertex-degree at most two with this property, and show that the analogous result for digraphs fails.

We generalize Harrington-Marker-Shelah's Dilworth-style characterization of the existence of non-empty perfect antichains to co-analytic quasi-orders, establish the analogous theorem at the next definable cardinal, and consider generalizations beyond the first level of the projective hierarchy.

We give a complete description of the size of the conjugacy classes of the automorphism group of the random graph with respect to Christensen's Haar null ideal. It is shown that every non-Haar null class contains a translated copy of a nonempty portion of every compact set and that there are continuum many non-Haar null conjugacy classes. Our methods also yield a new proof of an old result of Truss., Comment: Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles

In order to understand the structure of the "typical" element of an automorphism group, one has to study how large the conjugacy classes of the group are. For the case when typical is meant in the sense of Baire category, Truss proved that there is a co-meagre conjugacy class in Aut(Q, <), the automorphism group of the rational numbers. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. We give a complete description of the size of the conjugacy classes of Aut(Q, <) with respect to this notion. In particular, we show that there exist continuum many non-Haar null conjugacy classes, illustrating that the random behaviour is quite different from the typical one in the sense of Baire category., Comment: Most of this work previously appeared in the first version of the paper arXiv:1705.07593 which was split into 3 articles, including arXiv:1808.06121

Following Darji, we say that a Borel subset $B$ of an abelian Polish group $G$ is Haar meager if there is a compact metric space $K$ and a continuous function $f : K \to G$ such that the preimage of the translate, $f^{-1}(B+g)$ is meager in $K$ for every $g \in G$. The set $B$ is called strongly Haar meager if there is a compact set $C \subseteq G$ such that $(B+g) \cap C$ is meager in $C$ for every $g \in G$. The main open problem in this area is Darji's question asking whether these two notions are the same. Even though there have been several partial results suggesting a positive answer, in this paper we construct a counterexample. More specifically, we construct a $G_\delta$ set in $\mathbb{Z}^\omega$ that is Haar meager but not strongly Haar meager. We also show that no $F_\sigma$ counterexample exists, hence our result is optimal.

We study the quasi-order of topological embeddability on definable functions between Polish zero-dimensional spaces. We first study the descriptive complexity of this quasi-order restricted to the space of continuous functions. Our main result is the following dichotomy: the embeddability quasi-order restricted to continuous functions from a given compact space to another is either an analytic complete quasi-order or a well-quasi-order. We then turn to the existence of maximal elements with respect to embeddability in a given Baire class. It is proved that the class of continuous functions is the only Baire class to admit a maximal element. We prove that no Baire class admits a maximal element, except for the class of continuous functions which admits a maximum element.

N. Hindman, I. Leader and D. Strauss proved that it is consistent that there is a finite colouring of $\mathbb R$ so that no infinite sumset $X+X=\{x+y:x,y\in X\}$ is monochromatic. Our aim in this paper is to prove a consistency result in the opposite direction: we show that, under certain set-theoretic assumptions, for any $c:\mathbb R\to r$ with $r$ finite there is an infinite $X\subseteq \mathbb R$ so that $c$ is constant on $X+X$., Comment: 12 pages, final version accepted for publication in the Proceedings of AMS (https://doi.org/10.1090/proc/14431). Paper 1129 on S. Shelah's list. Comments are very welcome

We show that there is no simple (e.g. finite or countable) basis for Borel graphs with infinite Borel chromatic number. In fact, it is proved that the closed subgraphs of the shift graph on $[\mathbb{N}]^{<\mathbb{N}}$ with finite (or, equivalently, $\leq 3$) Borel chromatic number form a $\mathbf{\Sigma}^1_2$-complete set. This answers a question of Kechris and Marks and strengthens several earlier results.

Machine learning techniques have become increasingly popular in the field of resting state fMRI (functional magnetic resonance imaging) network based classification. However, the application of convolutional networks has been proposed only very recently and has remained largely unexplored. In this paper we describe a convolutional neural network architecture for functional connectome classification called connectome-convolutional neural network (CCNN). Our results on simulated datasets and a publicly available dataset for amnestic mild cognitive impairment classification demonstrate that our CCNN model can efficiently distinguish between subject groups. We also show that the connectome-convolutional network is capable to combine information from diverse functional connectivity metrics and that models using a combination of different connectivity descriptors are able to outperform classifiers using only one metric. From this flexibility follows that our proposed CCNN model can be easily adapted to a wide range of connectome based classification or regression tasks, by varying which connectivity descriptor combinations are used to train the network., Comment: 25 pages, 4 figures, 1 table, plus supplementary material

In order to understand the structure of the `typical' element of an automorphism group, one has to study how large the conjugacy classes of the group are. When typical is meant in the sense of Baire category, a complete description of the size of the conjugacy classes has been given by Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behavior of the automorphisms is entirely different from the Baire category case. In this paper, we generalize the theorems of Dougherty and Mycielski about $S_\infty$ to arbitrary automorphism groups of countable structures isolating a new model theoretic property, the Cofinal Strong Amalgamation Property. As an application we show that a large class of automorphism groups can be decomposed into the union of a meager and a Haar null set.

In order to understand the structure of the "typical" element of a homeomorphism group, one has to study how large the conjugacy classes of the group are. When typical means generic in the sense of Baire category, this is well understood, see e.g. the works of Glasner and Weiss, and Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. When typical means random, that is, almost every with respect to this notion of Haar null sets, the behaviour of the homeomorphisms is entirely different from the generic case. For $\text{Homeo}^+([0,1])$ we describe the non-Haar null conjugacy classes and also show that their union is co-Haar null, for $\text{Homeo}^+(\mathbb{S}^1)$ we describe the non-Haar null conjugacy classes, and for $\mathcal{U}(\ell^2)$ we show that, apart from the classes of the multishifts, all conjugacy classes are Haar null. As an application we affirmatively answer the question whether these groups can be written as the union of a meagre and a Haar null set.

We investigate families of subsets of $\omega$ with almost disjoint refinements in the classical case as well as with respect to given ideals on $\omega$. More precisely, we study the following topics and questions: 1) Examples of projective ideals. 2) We prove the following generalization of a result due to J. Brendle: If $V\subseteq W$ are transitive models, $\omega_1^W\subseteq V$, $\mathcal{P}(\omega)\cap V\not = \mathcal{P}(\omega)\cap W$, and $\mathcal{I}$ is an analytic or coanalytic ideal coded in $V$, then there is an $\mathcal{I}$-almost disjoint refinement ($\mathcal{I}$-ADR) of $\mathcal{I}^+\cap V$ in $W$, that is, a family $\{A_X:X\in\mathcal{I}^+\cap V\}\in W$ such that (i) $A_X\subseteq X$, $A_X\in \mathcal{I}^+$ for every $X$ and (ii) $A_X\cap A_Y\in\mathcal{I}$ for every distinct $X$ and $Y$. 3) The existence of perfect $\mathcal{I}$-almost disjoint ($\mathcal{I}$-AD) families, and the existence of a "nice" ideal $\mathcal{I}$ on $\omega$ with the property: Every $\mathcal{I}$-AD family is countable but $\mathcal{I}$ is nowhere maximal. 4) The existence of $(\mathcal{I},\text{Fin})$-almost disjoint refinements of families of $\mathcal{I}$-positive sets in the case of everywhere meager (e.g. analytic or coanalytic) ideals. We prove a positive result under Martin's Axiom. 5) Connections between classical properties of forcing notions and adding mixing reals (and mixing injections), that is, a (one-to-one) function $f:\omega\to\omega$ such that $|f[X]\cap Y|=\omega$ for every $X,Y\in [\omega]^\omega\cap V$.

Let $(G,\cdot)$ be a Polish group. We say that a set $X \subset G$ is Haar null if there exists a universally measurable set $U \supset X$ and a Borel probability measure $\mu$ such that for every $g, h \in G$ we have $\mu(gUh)=0$. We call a set $X$ naively Haar null if there exists a Borel probability measure $\mu$ such that for every $g, h \in G$ we have $\mu(gXh)=0$. Generalizing a result of Elekes and Stepr\=ans, which answers the first part of Problem FC from Fremlin's list, we prove that in every abelian Polish group there exists a naively Haar null set that is not Haar null.