Dr. Julia Boettcher - soviel Zeit muss sein ;-)

AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

One central topic in extremal graph theory is the question how certain
local properties enforce a specific global structure in a graph. Results
in this direction are particularly valuable when it is computationally
difficult to decide whether a graph has this global structure. Dirac's
theorem for example states that every n-vertex graph G with minimum degree
at least n/2 (local property) contains a Hamilton cycle (global
structure). The conjecture of Bollobas and Komlos replaces the Hamilton
cycle in this result by an arbitrary spanning bounded degree graph H of
small bandwidth and addresses the question which minimum degree enforces a
copy of H in G.

In this talk I will discuss the conjecture of Bollobas and Komlos and
explain which graphs H it covers, that is, I will provide a
characterisation for bounded degree graphs of small bandwidth. In addition
I will consider different variations of this result that weaken the
minimum degree condition on G or/and consider non-spanning graphs H, and
explain a related problem concerning the robustness of sparse random
graphs.

The regularity lemma of Szemeredi proved to be a valuable tool for solving
graph embedding problems of this type. If time permits I will also discuss
some of the central ideas in the proofs of the results mentioned above and
explain the role the regularity lemma in these proofs.

This talk is based on joint work with Peter Allen, Peter Heinig, Jan
Hladky, Yoshiharu Kohayakawa, Sybille Mueller, Klaas Pruessmann, Mathias
Schacht, Anusch Taraz, Andreas Wuerfl.

Benjamin Doerr

--email hidden

passcode not visible

logged in users only