Hyperfiniteness and Borel combinatorics

  • Clinton T. Conley

    Carnegie Mellon University, Pittsburgh, USA
  • Steve Jackson

    University of North Texas, Denton, USA
  • Andrew S. Marks

    University of California Los Angeles, USA
  • Brandon Seward

    Courant Institute of Mathematical Sciences, New York, USA
  • Robin D. Tucker-Drob

    Texas A&M University, College Station, USA
Hyperfiniteness and Borel combinatorics cover

A subscription is required to access this article.


We study the relationship between hyperfiniteness and problems in Borel graph combinatorics by adapting game-theoretic techniques introduced by Marks to the hyperfinite setting. We compute the possible Borel chromatic numbers and edge chromatic numbers of bounded degree acyclic hyperfinite Borel graphs and use this to answer a question of Kechris and Marks about the relationship between Borel chromatic number and measure chromatic number. We also show that for every there is a -regular acyclic hyperfinite Borel bipartite graph with no Borel perfect matching. These techniques also give examples of hyperfinite bounded degree Borel graphs for which the Borel local lemma fails, in contrast to the recent results of Csóka, Grabowski, Máthé, Pikhurko, and Tyros.

Related to the Borel Ruziewicz problem, we show there is a continuous paradoxical action of on a Polish space that admits a finitely additive invariant Borel probability measure, but admits no countably additive invariant Borel probability measure. In the context of studying ultrafilters on the quotient space of equivalence relations under AD, we also construct an ultrafilter on the quotient of which has surprising complexity. In particular, Martin’s measure is Rudin–Keisler reducible to .

We end with a problem about whether every hyperfinite bounded degree Borel graph has a witness to its hyperfiniteness which is uniformly bounded below in size.

Cite this article

Clinton T. Conley, Steve Jackson, Andrew S. Marks, Brandon Seward, Robin D. Tucker-Drob, Hyperfiniteness and Borel combinatorics. J. Eur. Math. Soc. 22 (2020), no. 3, pp. 877–892

DOI 10.4171/JEMS/935