Borel chromatic numbers

DOI10.1006/aima.1998.1771zbMath0918.05052OpenAlexW2073081340MaRDI QIDQ1279827

Alexander S. Kechris, Slawomir Solecki, Stevo Todorčević

Publication date: 19 August 1999

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/aima.1998.1771

zbMATH Keywords

Borel sets Borel function Borel space Borel chromatic number Borel coloring Borel graphs uncountable Borel number

Mathematics Subject Classification ID

Descriptive set theory (03E15) Coloring of graphs and hypergraphs (05C15)

Related Items

Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Measurable graph combinatorics ⋮ Borel fractional colorings of Schreier graphs ⋮ A dichotomy for Polish modules ⋮ Borel asymptotic dimension and hyperfinite equivalence relations ⋮ A Bayesian game without $\epsilon$-equilibria ⋮ Approximate Schreier decorations and approximate Kőnig's line coloring theorem ⋮ Acyclicity and reduction ⋮ Descriptive chromatic numbers of locally finite and everywhere two-ended graphs ⋮ Descriptive Kakutani equivalence ⋮ Borel chromatic number of closed graphs ⋮ BASIS THEOREMS FOR NON-POTENTIALLY CLOSED SETS AND GRAPHS OF UNCOUNTABLE BOREL CHROMATIC NUMBER ⋮ On minimal non-potentially closed subsets of the plane ⋮ On $n$-saturated closed graphs ⋮ A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension ⋮ A generalization of the 𝔾0 dichotomy and a strengthening of the 𝔼0ℕ dichotomy ⋮ Borel circle squaring ⋮ Same graph, different universe ⋮ A Borel chain condition of $T(X)$ ⋮ Finite versus infinite: an insufficient shift ⋮ Borel structurability on the 2-shift of a countable group ⋮ Extending the reach of the point-to-set principle ⋮ Continuous 2-colorings and topological dynamics ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Essential countability of treeable equivalence relations ⋮ Definable Kőnig theorems ⋮ ON THE EXISTENCE OF LARGE ANTICHAINS FOR DEFINABLE QUASI-ORDERS ⋮ First-order limits, an analytical perspective ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Injective tests of low complexity in the plane ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Lebesgue orbit equivalence of multidimensional Borel flows: A picturebook of tilings ⋮ Measurable chromatic and independence numbers for ergodic graphs and group actions ⋮ Point processes, cost, and the growth of rank in locally compact groups ⋮ Baire measurable paradoxical decompositions via matchings ⋮ Basis theorems for continuous $n$-colorings ⋮ Groups and dynamics: topology, measure, and Borel structure. Abstracts from the workshop held January 16--22, 2022 ⋮ Mini-workshop: Descriptive combinatorics, LOCAL algorithms and random processes. Abstracts from the mini-workshop held February 13--19, 2022 ⋮ KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS ⋮ Dichotomy theorems for countably infinite dimensional analytic hypergraphs ⋮ Equivariant maps to subshifts whose points have small stabilizers ⋮ Descriptive complexity of countable unions of Borel rectangles ⋮ Shift graphs on precompact families of finite sets of natural numbers ⋮ Perfect matchings as IID factors on non-amenable groups ⋮ Krieger's finite generator theorem for actions of countable groups. I. ⋮ Means on equivalence relations ⋮ Limits of locally-globally convergent graph sequences ⋮ The shift graph and the Ramsey degree of $[\mathbb N^\omega$] ⋮ Marked groups with isomorphic Cayley graphs but different Borel combinatorics ⋮ On the non-existence of mad families ⋮ A descriptive construction of trees and Stallings’ theorem ⋮ Free minimal actions of countable groups with invariant probability measures ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ JUMP OPERATIONS FOR BOREL GRAPHS ⋮ Baire-class $\xi $ colorings: The first three levels ⋮ The graph-theoretic approach to descriptive set theory ⋮ A complexity problem for Borel graphs ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ On the existence of small antichains for definable quasi-orders ⋮ Følner tilings for actions of amenable groups ⋮ Borel chromatic numbers of graphs of commuting functions ⋮ Separation of analytic sets by rectangles of low complexity ⋮ An antibasis result for graphs of infinite Borel chromatic number ⋮ Finite graphs and amenability ⋮ Compact graphings ⋮ MEASURABLE PERFECT MATCHINGS FOR ACYCLIC LOCALLY COUNTABLE BOREL GRAPHS ⋮ Measurable versions of Vizing's theorem ⋮ Borel oracles. An analytical approach to constant-time algorithms ⋮ BROOKS’ THEOREM FOR MEASURABLE COLORINGS ⋮ Ultraproducts of measure preserving actions and graph combinatorics ⋮ Pointwise ergodic theorems beyond amenable groups ⋮ Canonical forms of shift-invariant maps on $[\mathbb N^{\infty}$] ⋮ Equivalence relations that act on bundles of hyperbolic spaces ⋮ Polishness of some topologies related to word or tree automata ⋮ A determinacy approach to Borel combinatorics ⋮ Ends of graphed equivalence relations. I ⋮ Krieger’s finite generator theorem for actions of countable groups III ⋮ Countable abelian group actions and hyperfinite equivalence relations ⋮ The existence of measures of a given cocycle, I: atomless, ergodic σ-finite measures ⋮ Weak Borel chromatic numbers ⋮ Entropy, Shannon orbit equivalence, and sparse connectivity ⋮ Some recollections on early work with Jan Pelant ⋮ Positive entropy actions of countable groups factor onto Bernoulli shifts ⋮ Combinatorial Dichotomies in Set Theory ⋮ Invariant random subgroups of the free group ⋮ MEASURABLE REALIZATIONS OF ABSTRACT SYSTEMS OF CONGRUENCES ⋮ On the existence of cocycle-invariant Borel probability measures ⋮ Hyperfiniteness and Borel combinatorics ⋮ Hypergraphs and proper forcing ⋮ A SEPARATION RESULT FOR COUNTABLE UNIONS OF BOREL RECTANGLES ⋮ Potential Wadge classes ⋮ Krieger's finite generator theorem for actions of countable groups. II ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Uniform hyperfiniteness ⋮ Invariant Schreier decorations of unimodular random networks ⋮ Measurable chromatic numbers ⋮ Borel colouring bad rays ⋮ Scrambled Cantor sets ⋮ Measurable equidecompositions for group actions with an expansion property ⋮ Hurewicz-like tests for Borel subsets of the plane ⋮ Equitable colourings of Borel graphs ⋮ On Baire measurable colorings of group actions ⋮ Uniformity, universality, and computability theory ⋮ Haar-$\mathcal I$ sets: looking at small sets in Polish groups through compact glasses

Cites Work