2-dimensional Convexity Numbers and P 4-free Graphs

Geschke, Stefan

Canadian mathematical bulletin, Tome 57 (2014) no. 1, pp. 61-71

Résumé

For $S\,\subseteq \,{{\mathbb{R}}^{n}}$ a set $C\,\subseteq \,S$ is an $m$ -clique if the convex hull of no $m$ -element subset of $C$ is contained in $S$ . We show that there is essentially just one way to construct a closed set $S\,\subseteq \,{{\mathbb{R}}^{2}}$ without an uncountable 3-clique that is not the union of countably many convex sets. In particular, all such sets have the same convexity number; that is, they require the same number of convex subsets to cover them. The main result follows from an analysis of the convex structure of closed sets in ${{\mathbb{R}}^{2}}$ without uncountable 3-cliques in terms of clopen, ${{P}_{4}}$ -free graphs on Polish spaces.

Détail

DOI : 10.4153/CMB-2012-031-5

Mots-clés : 52A10, 03E17, 03E75, convex cover, convexity number, continuous coloring, perfect graph, cograph