Kechris, A. S. and Solecki, S. and Todorcevic, S.
(1999)
*Borel Chromatic Numbers.*
Advances in Mathematics, 141
(1).
pp. 1-44.
ISSN 0001-8708.
doi:10.1006/aima.1998.1771.
https://resolver.caltech.edu/CaltechAUTHORS:20130517-100529842

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20130517-100529842

## Abstract

We study in this paper graph coloring problems in the context of descriptive set theory. We consider graphs G=(X, R), where the vertex set X is a standard Borel space (i.e., a complete separable metrizable space equipped with its σ-algebra of Borel sets), and the edge relation R ⊆ X^2 is "definable", i.e., Borel, analytic, co-analytic, etc. A Borel n-coloring of such a graph, where 1⩽ n ⩽ N_0 , is a Borel map c: X → Y with card(Y)=n, such that xRy⇒c(x) ≠ {c( y). If such a Borel coloring exists we define the Borel chromatic number of G, in symbols X_B(G), to be the smallest such n. Otherwise we say that G has uncountable Borel chromatic number, in symbols X_B(G) > N_0.

Item Type: | Article | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||

Additional Information: | © 1999 by Academic Press. Received November 16, 1996; accepted April 30, 1998. The author acknowledges the support of the Mathematics Department at Caltech during his visits in January 1992 and 1995, the NSERC of Canada, and the Science Foundation of Serbia. Research partially supported by NSF Grant DMS-9317509. We thank A. Ditzen for allowing us to include the joint result 1.1 and A. Louveau for 8.2. | ||||||||||

Funders: |
| ||||||||||

Issue or Number: | 1 | ||||||||||

DOI: | 10.1006/aima.1998.1771 | ||||||||||

Record Number: | CaltechAUTHORS:20130517-100529842 | ||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20130517-100529842 | ||||||||||

Official Citation: | A.S Kechris, S Solecki, S Todorcevic, Borel Chromatic Numbers, Advances in Mathematics, Volume 141, Issue 1, 15 January 1999, Pages 1-44, ISSN 0001-8708, 10.1006/aima.1998.1771. (http://www.sciencedirect.com/science/article/pii/S0001870898917716) | ||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||

ID Code: | 38554 | ||||||||||

Collection: | CaltechAUTHORS | ||||||||||

Deposited By: | Ruth Sustaita | ||||||||||

Deposited On: | 22 May 2013 17:01 | ||||||||||

Last Modified: | 09 Nov 2021 23:38 |

Repository Staff Only: item control page