Clopen graphs

Stefan Geschke¹

¹ ausdorff Center for Mathematics Endenicher Allee 62 53115 Bonn, Germany

Fundamenta Mathematicae, Tome 220 (2013) no. 2, pp. 155-189

Résumé

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^2$ 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 $\omega^\omega$ with eventual domination. In particular, the dominating number $\mathfrak d$ 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 $\aleph_0$-saturated clopen graphs on $\omega^\omega$, while no $\aleph_1$-saturated graph embeds into a clopen graph on a Polish space. There is, however, an $\aleph_1$-saturated $F_\sigma$ graph on $2^\omega$.

Détail

DOI : 10.4064/fm220-2-5

Keywords: graph topological space its set vertices clopen edge relation clopen subset without diagonal study clopen graphs polish spaces terms their finite induced subgraphs obtain information about their cochromatic numbers context investigate modular profinite graphs class graphs obtained finite graphs taking inverse limits continues investigation continuous colorings polish spaces their homogeneity numbers started clopen graphs compact spaces have infinite induced subgraphs saturated particular there countably infinite graphs rados random graph embed clopen graph compact space using similar methods quasi orders clopen graphs compact zero dimensional metric spaces topological combinatorial embeddability tukey equivalent omega omega eventual domination particular dominating number mathfrak least size family clopen graphs compact metric spaces every clopen graph compact zero dimensional metric space embeds member family there aleph saturated clopen graphs omega omega while aleph saturated graph embeds clopen graph polish space there however aleph saturated sigma graph omega