On three parameters measuring non-convexity

Jul 23, 2016

Sprecher:innen

Über

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

Organisator

Kategorien

Über The Mathematics of Jiří Matoušek

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

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? The Mathematics of Jiří Matoušek folgen