BOREL CHROMATIC NUMBERS

BOREL CHROMATIC NUMBERS
复制标题

Borel 色数

DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Todorcevic
S. Todorcevic
中科院分区：
--
文献类型：
--
作者：
A. Kechris;Slawomir Solecki;S. Todorcevic

文献摘要

被引文献

相似文献

本文在描述集合论的背景下研究图的着色问题。我们考虑图G=(X，R)，其中顶点集X是标准Borel空间(即，具有其Borel集的σ-代数的完全可分度量空间)，且边关系R⊆X^2是 “可定义的”，即波雷尔、解析、共解析等。 这样一个图的Borel n-着色，其中1⩽n⩽N_0是一个Borel映射c：X→Y，且卡片(Y)=n，这样 那个xray⇒c(X)≠{c(Y).如果存在这样的Borel染色，我们定义Borel 在符号X_B(G)中，G的色数是这样的n中最小的一个。 否则，我们称G在符号X_B(G)&GT；N_0中有不可数的Borel色数。
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.