Vorträge

The blow-up lemma of Komlós, Sárközy and Szemerédi is an important tool for embedding large graphs H into dense graphs G. We recently obtained versions of this lemma for subgraphs G of sparse random and pseudo-random graphs. This has important applications in extremal graph theory on random graphs, but can also be used for the analysis of certain maker-breaker games.

In the talk I will explain our blow-up lemmas and describe their connection to maker-breaker games, after giving some necessary background.

Joint work with P. Allen, H. Hàn, Y. Kohayakawa, Y. Person.

High dimensionalities are a major roadblock for the numerical solution of problems in computational sciences. Straightforward discretizations are severely limited by the curse of dimensionality, the exponential dependency of the overall computational effort on the number of dimensions. It is therefore typically not feasible to treat more than four dimensions. In this talk, I will give a short introduction to Sparse Grids, which provide a versatile way to overcome the curse of dimensionality to a large extent, and show some of their applications. A special focus will be on spatially adaptive refinement, which adapts to the peculiarities of the problem at hand, and on adapted basis functions. Both are crucial whenever only few grid points can be spent, or where real-world problems do not meet the underlying smoothness requirements. The hierarchical basis formulation of the direct Sparse Grid approach conveniently provides a reasonable criterion for spatially adaptive refinement practically for free. This can serve as a starting point to develop suitable and problem-adapted modifications.

In this talk we survey the research activities and interests of the discrete maths group at TUHH.
We will discuss various topics such as colourings of embeddable graphs and hypergraphs, computational convexity, minimum bisection problems, and random graphs.

This talk gives an overview of some classical and recent uniqueness results in Discrete Tomography. In the first part we will review the concept of J-additivity and apply it to settle a problem of Kuba on 3-dimensional lattice sets and a conjecture of Brunetti and Daurat on planar lattice convex sets. The second part of the talk deals with the computational complexity of finding a smallest set of lattice positions of a given lattice set whose disclosure yields uniqueness w.r.t. some given X-rays. It turns out that this problem is already NP-hard in the plane and for the two standard directions.

This is joint work with Peter Gritzmann and Markus Wiegelmann.