Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, January 27, 2014

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Pavle Blagojević - FU Berlin, MI SANU Belgrade

Tverberg's theorem strikes back

Many of the strengthenings and extensions of the topological Tverberg theorem can be derived with surprising ease directly from the original theorem: For this we present new proof technique that combines a concept of "Tverberg unavoidable subcomplexes" with the observation that Tverberg points that equalize the distance from such a subcomplex can be obtained from maps to an extended target space.

Thus we obtain simple proofs for many variants of the topological Tverberg theorem, such as the colored Tverberg theorem of Zivaljevic and Vreica (1992). We also get a new strengthened version of the generalized van Kampen-Flores theorem by Sarkaria (1991) and Volovikov (1996), an affine version of their "j-wise disjoint" Tverberg theorem, and a topological version of Soberon's (2013) result on Tverberg points with equal barycentric coordinates.

(joint work with Florian Frick and Günter Ziegler)

Colloquium - 16:00

Moritz Firsching - FU Berlin

Applications of quadratically constrained programming in discrete geometry

We discuss two new applications of quadratically constraint programming in discrete geometry:

i) Given two 3-dimensional polyhedra P and Q, we can ask for the largest polyhedron similar to Q that is contained in P. Taking P and Q to be one of the 5 regular polyhedra we obtain 20 non-trivial pairs of polyhedra. H.T.Croft found the solution to this question in 14 out of these 20 cases. We show how quadratically constraint programming can be used to solve the remaining cases and check Croft's solution numerically. We discuss how exact solutions may be found with help of these computations.

ii) Given a planar graph (with specified combinatorial embedding) and weights for the inner faces we can ask for a straight line planar embedding of the graph such that the area of the inner faces of the embedding equals the prescribed weights. Such embeddings do not always exists, and are not necessarily unique if they do exist. We indicate how to use quadratically constraint programming to check if embeddings exist and to search for optimal embeddings in case they exist. We apply this tool in the case of 4-connected triangulations of the triangle with all equal ares. Taking the graph to be the grid graph and prescribing extra conditions on the boundary of the outer face we obtain the problem of table cartograms.

Letzte Aktualisierung: 16.01.2014