9 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…
From descriptive to distributed
Jan Grebík, Zoltán Vidnyánszky
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 alg…
Complexity of Linear Equations and Infinite Gadgets
Jan Grebík, Zoltán Vidnyánszky
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…
Hyperfiniteness on Topological Ramsey Spaces
Balázs Bursics, Zoltán Vidnyánszky
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}…
The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
Tamás Kátay, László Márton Tóth, Zoltán Vidnyánszky
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 -- pres…
Ramsey, expanders, and Borel chromatic numbers
Jan Grebík, Zoltán Vidnyánszky
We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.