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
Abstract:
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
Abstract:
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.