Menü

Forschungsseminar Diskrete 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, 12:30-13:45 Prof. Dr. Taraz, Andreas Würfl

Konkrete Vortragstermine können von diesen Zeiten abweichen.

## Vorträge

 Datum Vortragende(r) Thema Zeit/Raum Mi 26.10. Elad Aigner-Horev K_5 subdivisions in graphs - an overview of the Kelmans-Seymour conjecture (abstract) 10:15 Uhr,   MI 02.06.020 Do 03.11. Peter Heinig An asymptotic answer to a special case of an open conjecture of Bondy (abstract) 12:30 Uhr,   MI 02.06.020 Mi 09.11. Marc Noy Maximum degree in minor-closed classes of graphs (abstract) 10:15 Uhr,   MI 02.06.020 Do 17.11. Oliver Cooley Matchings, tight paths and tight cycles in k-uniform hypergraphs (abstract) 12:30 Uhr,   MI 02.06.020 Do 24.11. Piotr Śniady Open enumerative problems originating from asymptotic representation theory (abstract) 12:30 Uhr,   MI 02.06.020 Do 01.12. Yoshiharu Kohayakawa Universality of random graphs 12:30 Uhr,   MI 02.06.020 Do 08.12. Seminar fällt aus wegen Dies Academicus 12:30 Uhr,   MI 02.06.020 Mi 14.12. Julia Böttcher Tight Hamilton cycles in random hypergraphs (abstract) 10:15 Uhr,   MI 02.06.020 Do 22.12. Julia Ehrenmüller Colin de Verdières Invariante als Kriterium für planare Graphen (abstract) 12:30 Uhr,   MI 02.06.020 Do 19.01. Carl-Georg Heise Hypergraphen: Einbettungen als Simplizialkomplexe und Färbbarkeit (abstract) 12:30 Uhr,   MI 02.06.020 Do 26.01. Tina Schmidt Minimum Bisection (abstract) 12:30 Uhr,   MI 02.06.020 Do 26.01. Armin Krupp tba. 12:30 Uhr,   MI 02.06.020 Do 02.02. Hiep Han Turan problems for cycles in (pseudo-)random graphs (abstract) 12:30 Uhr,   MI 02.06.020 Do 09.02. Christoph Koch Subdivisions of K_5 - Mader's Theorem and the Kelmans-Seymour Conjecture (abstract) 12:30 Uhr,   MI 02.06.020

## Abstracts

### K_5 subdivisions in graphs - an overview of the Kelmans-Seymour conjecture

A refinement of Kuratowski's theorem, conjectured by Kelmans (1979) and Seymour (1975), postulates that \emph{a nonplanar $5$-connected graph contains a subdivision of $K_5$}.
This conjecture is a part of a line of research aiming at pinpointing the connectivity threshold beyond which precisely one of the Kuratowski graphs (i.e., subdivisions of $K_{3,3}$ and $K_5$) emerges in nonplanar graphs.
Kelmans and Thomassen (independently) proved that every $3$-connected nonplanar graph (on at least $6$ vertices) contains a subdivided $K_{3,3}$, and thus resolving the above threshold question for $K_{3,3}$. Despite several serious attempts made over the years to resolve it, the Kelmans-Seymour conjecture remains open.
In the past two years significant progress has been made towards a possible resolution of the Kelmans-Seymour conjecture. One of the aims of this talk is to survey the recent developments and to provide an account as to the current state of the art regarding this conjecture. If time permits, we shall make an attempt to overview some of the tools that were involved throughout the recent results.

### An asymptotic answer to a special case of an open conjecture of Bondy

This will be a short report on some recent partial progress on the following open question: In 1979 A. Bondy conjectured that for every $d\geq 3$ and every $3$-connected graph $X$ with minimum degree $\delta(X)\geq d$ and $n\geq 2d$ vertices, every circuit of $X$ can be realized as a symmetric difference of circuits each of which has length at least $2d-1$. It is still unknown whether this is true, and in published partial results it is assumed that, roughly, $n\geq 4d$. It seems to me that certain advances in contemporary extremal graph theory can be effectively brought to bear on this conjecture, at least when one allows oneself a minimum degree of $\delta(X)\geq (1+\gamma) d$ for an arbitrarily small $\gamma>0$ (this being the main reason for the adjective 'asymptotic'). While for bipartite graphs the strategy (which owes much to work of B. Alspach, S. C. Locke and D. Witte) of how to do this has been clear to me for three years by now, only quite recently I found a way to make it work in the case of arbitrary graphs with high minimum degree (and thus to have some bearing on Bondy's conjecture). I found a proof for a statement giving an asymptotic affirmative answer to the special case obtained when assuming that $n\geq 2d$' in Bondy's conjecture is true as $n = 2d$'. Moreover, if $n\geq 2d$' is true as $n = 2d+1$', then of the three circuit lengths $n-2$, $n-1$ and $n$ which are allowed by Bondy's conjecture, one can make do with $n$ alone (Hamilton circuits). In the talk I will outline the proof. A theorem of J. Böttcher, M. Schacht and A. Taraz guaranteeing spanning embeddings of low-bandwidth graphs into dense graphs plays a central role in the argument.

### Maximum degree in minor-closed classes of graphs

Given a class of graphs A closed under taking minors, we study the maximum degree Delta_n of random graphs from A with n vertices. We prove lower and upper bounds that hold with high probability, depending on the nature of the forbidden minors. In particular, we find orders of magnitude for Delta_n not observed before, such us logn / log log logn and logn / log log log logn. Our main tool is a counting argument introduced recently by McDiarmid and Reed for analyzing the maximum degree of random planar graphs.

### 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.

### Open enumerative problems originating from asymptotic representation theory

During the talk I will present some open problems which concern counting certain decorated graphs drawn on surfaces with given genus. Numerical experiments suggest that the generating polynomials for the number of such graphs ("Kerov character polynomials") have a very nice structure. The problems originate from asymptotic representation theory but they will be formulated in such a way that no knowledge of this topic is necessary. Everybody is very welcome to solve these problems.

### Tight Hamilton cycles in random hypergraphs

I present a polynomial time randomised algorithm that finds a k-uniform tight Hamilton cycle in a k-uniform random hypergraph with edge probability p=n^{eps-1} for every positive eps with high probability. The methods developed for solving this problem also have (more interesting) applications for finding powers of Hamilton cycles (and thus K_r-factors) in pseudorandom graphs, which I will also try to outline.

Joint work with Peter Allen, Hiep Han, Yoshiharu Kohayakawa, Yury Person.

### Colin de Verdières Invariante als Kriterium für planare Graphen

Yves Colin de Verdière führte 1990 eine Grapheninvariante μ(Γ) ein, die unter anderem zur Charakterisierung planarer Graphen dient. Die Hauptresultate sind: Γ ist planar genau dann wenn μ(Γ) <= 3. und Γ ist außerplanar genau dann wenn μ(Γ) <= 2.

Für die Definition der Invariante bedienen wir uns der Strong Arnolds hypothesis SAH. Anschließend betrachten wir seine Monotonieeigenschaft bezüglich Kontraktionen des Graphens, die ausschlaggebend für den Beweis des ersten obigen Satzes ist. Weiters behandeln wir die Eigenschaften der Invariante von sogenannten clique sums. Zum Abschluss beschäftigen wir uns noch mit n-kritischen Graphen, wobei ein Graph Γ mit n Knoten n-kritisch genannt wird, falls μ(Γ) = n und jeder Minor Γ1 von Γ (nicht-isomorph zu Γ) μ(Γ1) < n erfüllt.

### Hypergraphen: Einbettungen als Simplizialkomplexe und Färbbarkeit

Planare Graphen gehören wohl zu den beststudierten Objekten der Graphentheorie  wobei der 4-Farben-Satz hier als Höhepunkt betrachtet werden kann. Erste Verallgemeinerungen Graphen, welche auf speziellen Flächen einbettbar sind. Der Vortrag gibt eine Übersicht über mögliche Ideen, Hypergraphen (als Simplizialkomplexe) in den R^n einzubetten und damit Analoga zu planaren Graphen zu betrachten. Es liegt nun nahe, auch über weitere Verallgemeinerungen nachzudenken, nämlich ob die spezielle Eigenschaft einer konstanten chromatischen Oberschranke auch für andere Hypergraphen und in anderen Dimensionen gilt. Insbesondere betrachten wir den Fall eines k-uniformen Hypergraphen, welcher in den R^k eingebettet werden soll.

### Minimum Bisektion

Minimum Bisektion ist das NP-schwere Problem die Knoten eines Graphens in zwei gleich große Mengen zu partitionieren, sodass möglichst wenige Kanten zwischen diesen Mengen verlaufen. Beschränkt man sich auf planare Instanzen, so ist unbekannt, ob das Problem NP-schwer bleibt. Für Bäume - und auch allgemein für Graphen mit beschränkter Baumweite - kann eine exakte Lösung in polynomieller Zeit berechnet werden. In diesem Vortrag werde ich Baumzerlegungen und einige Eigenschaften davon erläutern, mit deren Hilfe man eine Bisektion konstruieren kann. Anschließend wird eine Vermutung über den Zusammenhang von großer Baumweite und großer Bisektionsweite in planaren Graphen vorgestellt.

### Turan problems for cycles in (pseudo-)random graphs

In the last decades, much effort has been dedicated to transferring classical results in Extremal Combinatorics to sparse (pseudo-)random settings. For example, the celebrated result of Green and Tao on arithmetic progressions in the prime perfectly fits such a framework. In this talk, we shall put emphasis on Turan-type questions and their extensions to sparse (pseudo-)random graphs. For the random setting, a breakthrough was achieved recently while for the pseudo-random setting the problem remains wide open. After an introduction we will discuss some of the problems, particularly we will address the ones mentioned in the title.

### Subdivisions of K_5 - Mader's Theorem and the Kelmans-Seymour Conjecture

In this talk I will come back to the topic of Elad's talk at the beginning of this semester. I will mainly focus on a variation of a proof for a theorem by Mader closely related to the Kelmans-Seymour Conjecture. This idea establishes a new approach towards a resolution of this conjecture. If time permits, I will also illustrate a computational approach to finding subdivisions of K_5 in 5-connected nonplanar graphs.

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

#### News

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.