4 papers
The ineffectiveness of the regularity lemma for bounded degree graphs
Clark Lyons, Grigory Terlov, Zoltán Vidnyánszky
We show that for any , there is no bound computable from on the size of a graph required to approximate a graph of maximum degree at most up to $\va…
Separating complexity classes of LCL problems on grids
Katalin Berlow, Anton Bernshteyn, Clark Lyons +1
We study the complexity of locally checkable labeling (LCL) problems on from the point of view of descriptive set theory, computability theory, and factors of i.i.d.…
Borel Families of Games
Alexander Kastner, Clark Lyons
We give an elementary proof that in a Borel family of games, the set of games for which player II has a winning strategy is Baire measurable, universally measurable, and completely…
Baire Measurable Matchings in Non-Amenable Graphs
Alexander Kastner, Clark Lyons
We prove that every Schreier graph of a free Borel action of a finitely generated non-amenable group admits a Baire measurable perfect matching, and that the Schreier graph of a fr…