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

Ehud Friedgut - Hebrew University

Exposing Dictatorships and Juntas

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

Alexander Engström - KTH Stockholm/TU Berlin

Resolutions of edge ideals

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.

Letzte Aktualisierung: 03.04.2008