# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

Monday, January 9, 2012

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005

Lecture - 14:15

### Graph regularity and removal lemmas

Abstract:
Szemerédi's regularity lemma is one of the most powerful tools in graph theory. It was introduced by Szemerédi in his proof of the celebrated Erdős-Turán conjecture on long arithmetic progressions in dense subsets of the integers. Roughly speaking, it says that every large graph can be partitioned into a small number of parts such that the bipartite subgraph between almost all pairs of parts is random-like. One of the most important applications is the graph removal lemma, which roughly says that every graph with few copies of a fixed graph H can be made H-free by removing few edges. It remains a significant problem to estimate the bounds in the regularity lemma and the removal lemma, and their variants. In this talk I discuss recent joint work with David Conlon which makes progress on this problem.

Colloquium - 16:00

### On the domination number of the random graph

Abstract:
A graph drawn from the random graph G(n,p) can be described in admirable detail. It turns out that many natural graph parameters, like the clique number, the independence number or the chromatic number are concentrated on two values when the edge probability p is large enough. The domination number D(G) of a graph G is the smallest cardinality of a vertex set S, such that every other vertex in G has an incident edge going into S. Wieland and Godbole proved that the domination number of G(n,p) is concentrated on two values if p is constant or just slightly sub-constant. We extend this result for the range when p is as small as ln^2n/ sqrt(n). We also indicate why some sort of a lower bound on the probability is necessary. Concentration, though not on a constant length interval can be proven for p as small as ln^2 n/n. This is joint work with Roman Glebov and Tibor Szabó.

Letzte Aktualisierung: 20.12.2011