Definable graphs and their applications

A recurring theme in mathematics is the interplay between the discrete and continuous. It is not surprising that infinite, continuous objects can be approximated by large finite ones. However, the ap- proximation of large finite objects by infinite ones turns out to be even more useful. In the past fifty years, perhaps due to the revolutionary changes brought about by information technology, the investigation of large networks has gained prominence. The mathematical models for these networks are graphs. Central notions of graph theory play a crucial role in information technology, programming, and computational complexity theory. If one generalizes finite graph-theoretic notions to infinite graphs in the most straightforward way, the latter often exhibit a counterintuitive, almost paradoxical behavior, quite different from that of the former. The reason underlying this contrasting behavior is that proofs of theorems concerning finite graphs can typically be translated to concrete procedures or algorithms, whereas analogous arguments concerning infinite graphs often lack this sort of constructibility. Hence, if our aim is to gain a better understanding of large finite graphs through the investigation of infinite ones, it is reasonable to require some sort of constructibility of the objects in question. The natural way to achieve this is to impose definability constraints on the infinite graph-theoretic notions. This is where finitary combinatorics and algorithms meet descriptive set theory, the study of the complexity of subsets of the real numbers. Our research will consider the structure of definable graphs. In particular, we will focus upon chromatic numbers and hyperfiniteness. Roughly speaking, the definable chromatic number of a graph is the minimal number of definable pieces into which the graph can be decomposed so that no two vertices from the same piece are related. Our aim is to understand whether, for a given number of pieces, there is a canonical obstacle to finding such a decomposition. Hyperfiniteness of a graph ensures that its vertex set can be decomposed into finite pieces in a particularly nice way. In this direction, we would like to know whether, given a notion of smallness and a graph, it is possible to find such a decomposition with a small exception.

The most important achievement of the project is the developed connection between the behavior of large finite and definable infinite networks. In the finite case, we worked with the LOCAL model of distributed computing. In this model, the nodes are imagined to be computers, which must make decisions (e.g., output a color, so that neighboring nodes output different colors) without exploring the entirety of the network - as it is imagined to be extremely large - only looking at their small neighborhoods. This ensures that there is no special node, or origin. The efficiency of a decision making algorithm is measured by the size of the neighborhood a given node has to explore. In the infinite case, the networks can be thought of as continuous analogues of the finite ones. In this situation, we require the decisions to be made in a continuous, or, more generally, definable way. This yields the same phenomenon, as in the finite situation: one will not be able to choose a single point from a given connected component of the network. This is the intuition behind the fact that these objects behave in a similar manner. While this intuitive analogy was clear for a long time, it was Bernshteyn`s work which developed a bridge between the two worlds. In our project, we investigated further aspects of these connections. One of our aims was to transfer the celebrated infinite game theoretic method of Marks to the finite world. In order to achieve this, we had to utilize non-trivial ideas from distributed computing, which, in turn, yielded new results back in the infinite context. This also resulted in a new way of constructing infinite graphs with interesting properties. Moreover, it turned out that some classes defined in the two fields in completely different manner, coincide. We believe we are only scratching the surface of a deep theory behind all these things, which hopefully will be explored and understood in the future.