On three parameters measuring non-convexity

by · Jul 23, 2016 · 327 views ·

Three measures of non-convexity of a set in Rd will be discussed. The invisibility graph I(X) of a set X⊆Rd 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 ω(I(X)), the chromatic number χ(I(X)) and the minimum number γ(X) of convex subsets of X that cover X. Observe that ω(X)≤χ(X)≤γ(X) for any set X, where ω(X):=ω(I(X)) and χ(X)=χ(I(X)). Here is a sample of results comparing the above three parameters: Let X⊆R2 be a planar set with ω(X)=ω<∞ and with no one-point holes. Then γ(X)≤O(ω4) . For every planar set X , γ(X) can be bounded in terms of χ(X) . There are sets X in R5 with χ(X)=3, but γ(X) arbitrarily large. The talk is based on joint papers with J. Matoušek, J. Cibulka, M. Korbelář, M. Kynčl, V. Mészáros, and R. Stolař.

Watch SlidesLive on mobile devices

© SlidesLive Inc.