Clopen graphs

Stefan Geschke. "Clopen graphs." Fundamenta Mathematicae 220.2 (2013): 155-189. <http://eudml.org/doc/282979>.

@article{StefanGeschke2013,
abstract = {A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their homogeneity numbers started in [11] and [9]. We show that clopen graphs on compact spaces have no infinite induced subgraphs that are 4-saturated. In particular, there are countably infinite graphs such as Rado’s random graph that do not embed into any clopen graph on a compact space. Using similar methods, we show that the quasi-orders of clopen graphs on compact zero-dimensional metric spaces with topological or combinatorial embeddability are Tukey equivalent to $ω^\{ω\}$ with eventual domination. In particular, the dominating number is the least size of a family of clopen graphs on compact metric spaces such that every clopen graph on a compact zero-dimensional metric space embeds into a member of the family. We also show that there are ℵ₀-saturated clopen graphs on $ω^\{ω\}$, while no ℵ₁-saturated graph embeds into a clopen graph on a Polish space. There is, however, an ℵ₁-saturated $F_\{σ\}$ graph on $2^\{ω\}$.},
author = {Stefan Geschke},
journal = {Fundamenta Mathematicae},
keywords = {clopen graph; local extremum; continuous function; measure; category; Polish spaces; cochromatic number; modular profinite graphs; inverse limits; quasi-order; Tukey equivalent; domination number; saturated clopen graphs},
language = {eng},
number = {2},
pages = {155-189},
title = {Clopen graphs},
url = {http://eudml.org/doc/282979},
volume = {220},
year = {2013},
}

TY - JOUR
AU - Stefan Geschke
TI - Clopen graphs
JO - Fundamenta Mathematicae
PY - 2013
VL - 220
IS - 2
SP - 155
EP - 189
AB - A graph G on a topological space X as its set of vertices is clopen if the edge relation of G is a clopen subset of X² without the diagonal. We study clopen graphs on Polish spaces in terms of their finite induced subgraphs and obtain information about their cochromatic numbers. In this context we investigate modular profinite graphs, a class of graphs obtained from finite graphs by taking inverse limits. This continues the investigation of continuous colorings on Polish spaces and their homogeneity numbers started in [11] and [9]. We show that clopen graphs on compact spaces have no infinite induced subgraphs that are 4-saturated. In particular, there are countably infinite graphs such as Rado’s random graph that do not embed into any clopen graph on a compact space. Using similar methods, we show that the quasi-orders of clopen graphs on compact zero-dimensional metric spaces with topological or combinatorial embeddability are Tukey equivalent to $ω^{ω}$ with eventual domination. In particular, the dominating number is the least size of a family of clopen graphs on compact metric spaces such that every clopen graph on a compact zero-dimensional metric space embeds into a member of the family. We also show that there are ℵ₀-saturated clopen graphs on $ω^{ω}$, while no ℵ₁-saturated graph embeds into a clopen graph on a Polish space. There is, however, an ℵ₁-saturated $F_{σ}$ graph on $2^{ω}$.
LA - eng
KW - clopen graph; local extremum; continuous function; measure; category; Polish spaces; cochromatic number; modular profinite graphs; inverse limits; quasi-order; Tukey equivalent; domination number; saturated clopen graphs
UR - http://eudml.org/doc/282979
ER -