| [home] - [up] |
Abstract: Over the last decades Szemer\'edi's regularity lemma has proven to be a very powerful tool in modern graph theory. Unfortunately, in its original setting it only gives nontrivial results for dense graphs, that is graphs with $\Theta(n^2)$ edges. In 1996 Kohayakawa and independently R\"odl introduced a variant which holds for sparse graphs, provided they satisfy some additional structural conditions (which essentially mean that the graph does not contain too dense spots). However, using this sparse regularity lemma to prove e.g.\ extremal and Ramsey type results similar to the known results in the dense case, requires as an additional step the existence of appropriate embedding or counting lemmas. For the sparse case this missing step has been formulated as a conjecture by Kohayakawa, \L{}uczak and R\"odl in 1996. In this talk we prove a weak version of the KLR-conjecture and present various applications in random graph theory.
Colloquium - 16:00
Abstract: The terminology of maps refers to graphs embedded on a surface. Like in the case of trees, rooted objects are easier to count than unrooted ones, which are subject to symmetries. In this talk we present a new method to count several families of unrooted maps on the sphere, using a decomposition of a map into a tree-structure. As a main application, we are able to count efficiently unrooted 3-connected maps, corresponding to oriented combinatorial polytopes in 3D-space.