A determinacy approach to Borel combinatorics

This note gives an informal overview of the proof in our paper "Borel Conjecture and Dual Borel Conjecture", see arXiv:1105.0823.

This paper has been withdrawn by the author due to an error.

We determine the consistency strength of determinacy for projective games of length $\omega^2$. Our main theorem is that $\boldsymbol\Pi^1_{n+1}$-determinacy for games of length $\omega^2$ implies the existence of a model of set theory with $\omega + n$ Woodin cardinals. In a first step, we show that this hypothesis implies that there is a countable set of reals $A$ such that $M_n(A)$, the canonical inner model for $n$ Woodin cardinals constructed over $A$, satisfies $A = \ma...

In this survey we give a concise introduction to a continuous version of Borel combinatorics. Our approach will have a certain algorithm-theoretic nature and we will give special emphasis to the notion of almost finiteness introduced by Matui as a continuous analogue of Borel hyperfiniteness. We also show how the theory can be used to study spectral convergence for graph Laplacians.

In this paper we extend previous studies of selection principles for families of open covers of sets of real numbers to also include families of countable Borel covers. The main results of the paper could be summarized as follows: 1. Some of the classes which were different for open covers are equal for Borel covers -- Section 1; 2. Some Borel classes coincide with classes that have been studied under a different guise by other authors -- Section 4.

Louveau showed that if a Borel set in a Polish space happens to be in a Borel Wadge class $\Gamma$, then its $\Gamma$-code can be obtained from its Borel code in a hyperarithmetical manner. We extend Louveau's theorem to Borel functions: If a Borel function on a Polish space happens to be a $\Sigma_t$-function, then one can effectively find its $\Sigma_t$-code hyperarithmetically relative to its Borel code. More generally, we prove extension-type, domination-type, and decompo...

We transform a Muller game with n vertices into a safety game with (n!)^3 vertices whose solution allows to determine the winning regions of the Muller game and to compute a finite-state winning strategy for one player. This yields a novel antichain-based memory structure and a natural notion of permissive strategies for Muller games. Moreover, we generalize our construction by presenting a new type of game reduction from infinite games to safety games and show its applicabil...

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.

We are concerned with the problem of witnessing the Baire property of the Borel and the projective sets (assuming determinacy) through a sufficiently definable function in the codes. We prove that in the case of projective sets it is possible to satisfy this for almost all codes using a continuous function. We also show that it is impossible to improve this to all codes even if more complex functions in the codes are allowed. We also study the intermediate steps of the Borel ...

This is an update on, and expansion of, our paper Open problems on $\beta\omega$ in the book Open Problems in Topology.