Monday, February 6, 2012
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041
Lecture - 14:15
The talk discusses planning problems where a set of items has to be transported from location A to location B subject to certain collision and/or resource constraints. We analyze the behavior of these problems, discuss their history, and derive some of their combinatorial and algorithmic properties.
Colloquium - 16:00
For every integer r>= 2 we call a k-uniform hypergraph H on n vertices r-Ramsey-forcing if every r-edge-coloring of K_n contains a monochromatic copy of K_k whose vertices form a hyperedge in H. We determine the threshold for a random k-uniform hypergraph on n vertices and edge probability q to be r- Ramsey-forcing. Further we discuss common features of the above problem with the more classical Ramsey's theorem for random (hyper-)graph G(n,p).
This is joint work with Luca Gugelmann, Angelika Steger and Henning Thomas.