We show that a locally finite Borel graph is nonsmooth if and only if it admits marker sequences which are far from every point. Our proof uses the Galvin-Prikry theorem and the Glimm-Effros dichotomy.
We provide a gentle introduction, aimed at non-experts, to Borel combinatorics that studies definable graphs on topological spaces. This is an emerging field on the borderline between combinatorics and descriptive set theory with deep connections to many other areas. After giving some background material, we present in careful detail some basic tools and results on the existence of Borel satisfying assignments: Bore
We give a completely constructive solution to Tarskis circle squaring problem. More generally, we prove a Borel version of an equidecomposition theorem due to Laczkovich. If $k geq 1$ and $A, B subseteq mathbb{R}^k$ are bounded Borel sets with the same positive Lebesgue measure whose boundaries have upper Minkowski dimension less than $k$, then $A$ and $B$ are equidecomposable by translations using Borel pieces. This answers a question of Wagon. Our proof uses ideas from the study of flows in graphs, and a recent result of Gao, Jackson, Krohne, and Seward on special types of witnesses to the hyperfiniteness of free Borel actions of $mathbb{Z}^d$.
Let $G=(V,E)$ be a locally finite graph. Firstly, using calculus of variations, including a direct method of variation and the mountain-pass theory, we get sequences of solutions to several local equations on $G$ (the Schrodinger equation, the mean field equation, and the Yamabe equation). Secondly, we derive uniform estimates for those local solution sequences. Finally, we obtain global solutions by extracting convergent sequence of solutions. Our method can be described as a variational method from local to global.
We prove that, for any natural number n $ge$ 1, we can find a finite alphabet $Sigma$ and a finitary language L over $Sigma$ accepted by a one-counter automaton, such that the $omega$-power L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L} is $Pi$ 0 n-complete. We prove a similar result for the class $Sigma$ 0 n .
A graph $G$ is said to be ubiquitous, if every graph $Gamma$ that contains arbitrarily many disjoint $G$-minors automatically contains infinitely many disjoint $G$-minors. The well-known Ubiquity conjecture of Andreae says that every locally finite graph is ubiquitous. In this paper we show that locally finite graphs admitting a certain type of tree-decomposition, which we call an extensive tree-decomposition, are ubiquitous. In particular this includes all locally finite graphs of finite tree-width, and also all locally finite graphs with finitely many ends, all of which have finite degree. It remains an open question whether every locally finite graph admits an extensive tree-decomposition.