Monday, January 9, 2012
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room 005
Lecture - 14:15
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
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ó.