On three parameters measuring non-convexity

23. Červenec 2016

Řečníci

O prezentaci

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

Organizátor

Kategorie

O organizátorovi (The Mathematics of Jiří Matoušek )

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

Uložení prezentace

Měla by být tato prezentace uložena po dobu 1000 let?

Jak ukládáme prezentace

Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte The Mathematics of Jiří Matoušek