Monday, January 27, 2014
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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.