On three parameters measuring non-convexity

Jul 23, 2016

Speakers

About

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ř.

Organizer

Categories

About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek