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

The Upcoming Monday Lecture and Colloquium

Monday, October 29, 2007

Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Michael Huber - Tübingen/Berlin

Flag-transitive Designs

Among the properties of homogeneity of incidence structures flag-transitivity obviously is a particularly important and natural one. Consequently, in the last decades flag-transitive Steiner t-designs (i.e. flag-transitive t-(v,k,1) designs) have been investigated, whereas only by the use of the classification of the finite simple groups has it been possible in recent years to essentially characterize all flag-transitive Steiner 2-designs. However, despite the finite simple group classification, for Steiner t-designs with parameters t > 2 such characterizations have remained challenging long-standing open problems. This talk presents the complete classification of all flag-transitive Steiner t-designs with t > 2. The result, which relies on the classification of the finite doubly transitive permutation groups, generalizes work by J. Tits (1964) and H. Lüneburg (1965). Besides group theory the proofs also involve incidence geometric, combinatorial and number theoretical arguments. The occurring examples and an outline of the proof with the most interesting parts shall be illustrated.

Colloquium - 16:00

Paul Bonsma - TU Berlin

Recent results on finding spanning trees with many leaves

This talk will be about the problem of finding spanning trees of a graph, where the goal is to maximize the number of leaves. I will give an overview of recent results on this problem: fast fixed parameter tractable algorithms, approximation algorithms, and lower bounds for the number of leaves that can be obtained in various graph classes.