ON THREE MEASURES OF NON-CONVEXITY

Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Autoři

CIBULKA Josef KORBELÁŘ Miroslav KYNCL Jan MESZAROS Viola STOLAR Rudolf CIBULKA J. VALTR Pavel

Rok publikování 2017
Druh Článek v odborném periodiku
Časopis / Zdroj Israel journal of mathematics
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www Full Text
Doi http://dx.doi.org/10.1007/s11856-017-1467-1
Klíčová slova CONVEX-SETS; DECOMPOSITION THEOREMS; SUBSETS; UNION; PLANE
Popis The invisibility graph I (X) of a set X subset of 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 Matousek 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.