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

Laszlo Szekely - University of South Carolina

Lovasz Local Lemma - a new tool for asymptotic enumeration?

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

Eva Czabarka - University of South Carolina

Multi-part Sperner systems

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

Letzte Aktualisierung: 14.10.2010