Charles Explorer logo
🇨🇿

On three measures on non-convexity

Publikace na Matematicko-fyzikální fakulta |
2017

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

The invisibility graph I(X) of a set X in 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)) >= log log(n) but omega(I(X))=3.

We also find sets X in R^5 with chi(X)=2, but gamma(X) arbitrarily large.