#
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

*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**

###
Marc Thurley - Humboldt Universität Berlin

###
Partition Functions

*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.

Letzte Aktualisierung:
21.12.2007