TUM - Mathematik

Angewandte Geometrie und Diskrete Mathematik

Auf dieser Seite werden die Vortragstermine im Forschungsseminar der Arbeitsgruppe Diskrete Mathematik verwaltet.

Standardtermine

Seminar:	MI 02.06.020, Do, 15:00-16:00
Organisation:	Prof. Dr. Taraz, Andreas Würfl

Einzelne Vortragstermine können von diesen Zeiten abweichen.

Vorträge

	Datum	Vortragende(r)	Thema	Zeit/Raum
Vortrag	Do 26.04.	Stefanie Gerke	H-factors in random graphs	15:00 Uhr, MI 02.06.020
Vortrag	Do 03.05.	Evgeny Zavalnyuk	Minimal fillings of the regular polygons on the Euclidean plane (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 10.05.	Marc Noy	On the probability of planarity of the random graph near the critical point (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 24.05.	Oliver Cooley	Hypergraph regularity for dummies (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 31.05.	Anusch Taraz	On packing many trees into the complete graph (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 14.06.	Andreas Würfl	Large planar subgraphs in dense graphs (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 21.06.	Tina Schmidt & Alexander Kampmeier	On Minimum Bisection of Graphs (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 05.07.	Susanne Nieß	Neues zum Ramsey Multiplicity Problem (abstract)	15:00 Uhr, MI 02.06.020
Vortrag	Do 12.07.	Armin Krupp	Über die chromatische Zahl bestimmter Graphen (abstract)	15:00 Uhr, MI 02.06.020

Abstracts

Evgeny Zavalnyuk: Minimal fillings of the regular polygons on the Euclidean plane

There are geometrical optimization problems that stand in close relation with discrete mathematics, and, in particular, with graph theory. As introduction we will state the well-known Steiner problem, which is to find a shortest tree interconnecting a finite set of points in a metric space.

The general problem of a minimal filling was formulated by M.Gromov. The task is to find a film that covers the given smooth closed manifold and has the least volume. If the dimension of the manifold is equal to 0, then the problem can be formulated in graph theoretic language: given a finite metric space, connect its points through a weighted graph satisfying some condition on the weight function and having the least weight. Such a graph turns out to be a tree.

The existence of a universal algorithm solving this problem is an open question. However, there are some results in the case where the metric space is in some sense symmetric. Given the finite metric space M, which is given by the vertices of a regular polygon on the Euclidean plane, let us look at the trees that can be embedded into the plane. Here we can find a tree T that delivers a minimal filling of M within the class of embedded trees. It still remains a conjecture that T delivers a minimal filling of M in general.

Marc Noy: On the probability of planarity of the random graph near the critical point

The random graph G(n,M) with n vertices and M edges changes abruptly around M = n/2, as established in 1960 by Erdös and Rényi. When M = n/2, Erdös and Rényi asked about the probability that G(n,n/2) is planar. It has been shown that the limiting probability

p = lim Pr{ G(n,n/2) is planar }

exists and is strictly between 0 and 1. In our work we determine the exact value p = 0.98003... In the proof we use structural properties of the random graph G(n,n/2) together with generating functions. We work more generally in the so-called critical window M = n/2 + x*n^(2/3), when x is a real number. We analyze too the probability that a random graph belongs to a class of graphs closed under minors. (Joint work with Vlady Ravelomanana and Juanjo Rusé.)

Matchings, tight paths and tight cycles in k-uniform hypergraphs

The Erdös-Gallai Theorem gives an upper bound on the number of edges in a graph which does not contain a matching of size r. We consider the analogous conjecture for k-uniform hypergraphs, for which partial results have been obtained by other researchers. In this talk I will describe how we were able to make progress on this problem by switching our attention from finding a matching of size r to the seemingly harder problem of finding a tight path, or even a tight cycle, on kr vertices. In the process, I will cautiously skim the surface of hypergraph regularity without diving down to the murky depths of detail. The talk is based on joint work with Peter Allen, Julia Böttcher and Richard Mycroft.

Anusch Taraz: On packing many trees into the complete graph

In 1976, Gyarfas and Lehel made the somewhat stunning conjecture that any family of trees T_1,T_2,...,T_n, with 1,2,...,n vertices respectively, can be packed in an edge-disjoint manner into the complete graph on n vertices. This conjecture is still open.

In this talk I will sketch a proof for a slightly weakened version of this conjecture, where we only consider trees of bounded maximum degree and allow the complete graph to have an additional o(n) vertices.

This is joint work with J.Böttcher, J.Hladky and D.Piguet.

Andreas Würfl: Large Planar Subgraphs in Dense Graphs

A graph is called planar if it can be drawn in the plane in such a way that its edges do not cross. We define the planarity of G to be the maximum number of edges in a planar subgraph of G. Finding such a maximum planar subgraph is a hard problem. Instead we will present lower bounds on the number of its edges. In particular we will be interested in the connection between minimum degree and planarity. This dependence has been studied before for various minimum degrees. So we were surprised to find a jump in the evolution of the planarity at minimum degree n/2.

This is joint work with T. Luczak and A. Taraz.

Tina Schmidt & Alexander Kampmeier: On Minimum Bisection of Graphs

Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two classes of equal size while minimizing the number of edges between those classes. It is unknown whether the problem remains NP-hard when restricted to planar graphs. The first talk is about the relationship of minimum bisection width and tree-width in planar graphs with bounded degree. First, an approach using separating vertices in trees to construct a bisection is presented. This approach can be generalized using either the Planar Separator Theorem or a tree decomposition. Together, these results imply for planar graphs with bounded degree that whenever the minimum bisection width is large, the tree-width must be large as well. Finally, an idea for a homogeneity condition is presented, which could be used to show that large tree-width implies large minimum bisection width. The second talk addresses graphs with bounded tree-width and presents an exact algorithm for the minimum bisection problem. This algorithm by Jansen et al has polynomial running time, when a tree-decomposition of constant width for the input graph is provided.

Neues zum Ramsey Multiplicity Problem

Für natürliche Zahlen n, t mit n > t kann man die Frage stellen: Wie viele einfarbige K_t gibt es mindestens in einer beliebigen Färbung des K_n mit 2 Farben? Nach Ramsey wissen wir, dass es für genügend großes n mehr als 0 sein müssen. Sonst aber ist bis jetzt bemerkenswert wenig bekannt. In diesem Vortrag soll der bisherige Wissensstand präsentiert und ein neues Ergebnis vorgestellt werden.

Über die chromatische Zahl bestimmter Graphen

Der Vortrag behandelt zwei verschiedene Problemstellungen: Im ersten Teil wird die chromatische Zahl von planaren Graphen mit Minimalgrad 5 betrachtet. Im zweiten Teil wird eine von der Knotenzahl abhängige obere Schranke für Graphen, deren pfadinduzierte Subgraphen dreifärbbar sind, bewiesen. Da beide Probleme noch nicht abschließend gelöst sind, sollen insbesondere aktuelle Beweisstrategien vorgestellt und besprochen werden.

Research Unit M9

Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics