Monday, April 14, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25,
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
The Erdös-Ko-Rado theorem is perhaps the most fundamental
theorem in extremal combinatorics. It characterizes maximal intersecting
families of k-subsets of {1,2, ...,n} when k < n/2.
The answer is a family of all sets containing a fixed element.
The famous Arrow impossibility theorem (for which Kenneth Arrow was
awarded the Nobel Prize in economics) states that under some mild and
reasonable restrictions the only possible way a society can aggregate
the preferences of all members of society is to let one individual
(a dictator) decide.
Is there a connection between these two theorems? Can they be proved using
analytical or algebraic tools rather than elementary combinatorics?
We will study these questions, and consider some other similar mathematical
situations.
We will also present in its entirety a beautiful and unexpected proof of
(a variant of) Arrow's theorem due to Gil Kalai. Kalai's proof uses Fourier
analysis, but we will state it in a self-contained manner without using the
word "Fourier".
Colloquium - 16:00
Abstract:
To a graph one can associate a monomial ideal generated by the x_ix_j for
which ij is an edge. A classical theorem by Fröberg states that the
resolution is linear exactly when the complement of the graph is chordal.
I will present a new proof of it and answer some questions raised by the
old one. Also some cellular resolutions will be touched upon. This is
joint work with Anton Dochtermann.