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

(FU) Freie Universität Berlin
Institut für Informatik
Takustr. 9,
14195 Berlin
room 005

Lecture - 14:15

Oleg Pikhurko, Carnegie Mellon University, Pittsburgh

Hypergraph Turan Problem


The Turan function of a given k-graph (that is, a k-uniform set system) F is the maximum number of edges in an F-free k-graph on n vertices. This problem goes back to the fundamental paper of Turan from 1941 who solved it for complete graphs. Unfortunately, when we move to k-graphs with k>2, then very few non-trivial instances of the problem have been solved. In particular, the problem of Turan from 1941 (also a $1000 question of Erdos) to determine the Turan function of the tetrahedron is still open in spite of decades of active attempts. In this talk we will survey some results and methods on the hypergraph Turan problem. In particular, we describe the recent progress on a tetrahedrom-related problem obtained by Razborov using his flag algebra technique as well as the corresponding exact result. Time permitting, we discuss the stability approach of Simonovits that greatly helps in converting asymptotic computations, such as those obtained via flag algebras or (hyper)graph limits, into exact results.

Colloquium - 16:00

Benjamin Lorenz - Freie Universitšt Berlin

Classification of Smooth Lattice Polytopes with few Lattice Points


Lattice polytopes appear in many different areas, for example in toric geometry where an interesting object of study are projective toric varieties and especially the smooth ones. This smoothness can again be found as an intrinsic property of the polytope defining the variety. Christian Haase et al have shown that there are only finitely many smooth lattice polytopes for fixed dimension and an upper bound on the number of lattice points in the polytope. Based on this proof I have developed an algorithm that can generate the list of all these smooth lattice polytopes given certain minimal smooth fans and an upper bound on the number of lattice points. The talk will give an outline of the proof of the finiteness and then discuss the classification algorithm.

Letzte Aktualisierung: 15.04.2010