On three measures of non-convexity

Abstract

The invisibility graph $I(X)$ of a set $X\subseteq {\mathbb{R}}^d$ is a (possibly infinite) graph whose vertices are the points of $X$ and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in $X$. We consider the following three parameters of a set $X$: the clique number $\omega (I(X))$, the chromatic number $\chi (I(X))$ and the convexity number $\gamma (X)$, which is the minimum number of convex subsets of $X$ that cover $X$. We settle a conjecture of Matoušek and Valtr claiming that for every planar set $X$, $\gamma (X)$ can be bounded in terms of $\chi (I(X))$. As a part of the proof we show that a disc with $n$ one-point holes near its boundary has $\chi (I(X))\ge \log \log (n)$ but $\omega (I(X))=3$. We also find sets $X$ in ${\mathbb{R}}^5$ with $\chi (X)=2$, but $\gamma (X)$ arbitrarily large.

28 pages, 9 figures; minor changes, added a few definitions and two references regarding metabelian groups

References in corpus (2)

• A note on order-type homogeneous point sets
• Coloring d-Embeddable k-Uniform Hypergraphs