Premium
Weak Borel chromatic numbers
Author(s) -
Geschke Stefan
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010001
Subject(s) - mathematics , combinatorics , clique number , chromatic scale , disjoint sets , discrete mathematics , critical graph , countable set , polish space , graph , graph power , line graph , mathematical analysis , separable space
Abstract Given a graph G whose set of vertices is a Polish space X , the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G ‐independent Borel sets that covers all of X . Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge. We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ 1 . We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA. Slightly weaker results hold for F σ ‐graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable F σ ‐graph has a Borel chromatic number of at most ℵ 1 . We refute various reasonable generalizations of these results to hypergraphs (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)