Open Collections

Description

Three measures of non-convexity of a set in $R^d$ will be discussed. The invisibility graph $I(X)$ of a set $X \subseteq 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 minimum number $\gamma(X)$ of convex subsets of $X$ that cover $X$. Observe that $\omega(X) \leq \chi(X) \leq \gamma(X)$ for any set $X$, where $\omega(X):=\omega(I(X))$ and $\chi(X)=\chi(I(X))$. Here is a sample of results comparing the above three parameters: 1. Let $X \subseteq R^2$ be a planar set with $\omega(X)=\omega < \infty$ and with no one-point holes. Then $\gamma(X) \leq O(\omega^4)$. 2. For every planar set $X$, $\gamma(X)$ can be bounded in terms of $\chi(X)$. 3. There are sets $X$ in $R^5$ with $\chi(X)=3$, but $\gamma(X)$ arbitrarily lar ge. The talk is based on joint papers with J. Cibulka, M. Korbel\'a\v r, M. Kyn\v cl, J. Matou\v sek, V. M\'esz\'aros, and R. Stola\v r.