Monday, November 15, 2010
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Straße des 17. Juni 136,
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Since 1975, the Lovasz Local Lemma has been the tool to
find the proverbial needle in the haystack. In a lopsided version,
dependency graphs may be replaced with negative dependency graphs.
We provide two constructions for negative dependency graphs that
are not dependency graphs. For these constructions, we provide
closely matching upper bounds for the term estimated in the Lovasz
Local Lemma.
As application, we derive asymptotic enumeration results for
permutations, Latin rectangles, and regular graphs. Although these
are not as good as the best current results, they would have been
the best in the 70's. This is joint work with Lincoln Lu.
Colloquium - 16:00
Abstract:
A Sperner system is an antichain in the subset lattice.
The maximum size of a Sperner system is $\binom{n}{\lfloor n/2\rfloor}$ on a universe of $n$ elements, and a maximum
size Sperner system is (one of the) middle levels in the subset lattice.
We will consider several generalizations of Sperner systems, and
obtain new results for them. We also show a new conjecture on multi-partite Sperner systems of maximum size.
This joint work with Harout Aydinian, P\'eter L. Erd\H os and
L\'aszl\'o A. Sz\'ekely