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 14, 2008

Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin
ATTENTION CHANGED: Haus I, 4. Etage, Raum 410.

Lecture - 14:15

Dhruv Mubayi - University of Illinois at Chicago and Carnegie Mellon University

Problems and results in extremal set theory

I will begin by introducing the broad subject of extremal set theory via some of its most beautiful and famous conjectures, and mentioning some applications. After this, we will turn our attention to questions about simplices and clusters, which are two natural generalizations of intersecting families. In the last part of the talk, I will give a proof of the following result, which settles a conjecture of Frankl and Furedi from the early 1980's: Suppose that n>3k/2 and G is a family of k-sets of an n-set of size greater than {n-1 choose k-1}. Then G contains three sets with union of size at most 2k and empty intersection.

Colloquium - 16:00

Marc Thurley - Humboldt Universität Berlin

Partition Functions

Partition functions have been developed in statistical physics to describe important thermodynamical properties of particle systems. Being weighted generalizations of graph homomorphism counting problems, their computational complexity has been studied exhaustively for the case of undirected graphs and non-negative weights. I will talk about new results which enable us to classify the complexity of partition functions for arbitrary real-valued weights. This is joint work with Leslie Ann Goldberg, Mark Jerrum and Martin Grohe.

Letzte Aktualisierung: 21.12.2007