July 9, 2007
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
The size-Ramsey number of a graph~$G$ is the smallest number of edges in a
graph~$\Gamma$ with the Ramsey property for~$G$, that is, with the property
that any colouring of the edges of~$\Gamma$ with two colours (say) contains a
monochromatic copy of~$G$. The study of size-Ramsey numbers was proposed by
Erd\H os, Faudree, Rousseau, and Schelp in~1978, when they investigated, for
example, the size-Ramsey number of star forests and raised some questions
concerning the size-Ramsey number of paths. In this talk, we shall survey
some results that have been discovered since, focusing on a couple of recent
results obtained by the study of Ramsey properties of fairly sparse random
graphs by means of the regularity lemma.
Colloquium - 16:00
Abstract:
Lovasz has conjectured the following: there exists a function f(k)
such that for every
f(k)-connected graph G and every pair of vertices u and v, there
exists a u-v path P such that G-V(P) is k-connected. Progress so far
on the conjecture has been restricted
to small values of k. The conjecture is true when k=1 due to a
theorem of Tutte, and was shown to also be true when k=2 independently
by Kriesell and Chen, Gould, and Yu.
We present recent work on two distinct weakenings of the conjecture.
In the first, we look for many disjoint u-v paths such that deleting
the vertices of all the paths leaves the graph connected. In the
second, we show that if G is sufficiently highly connected, there
exists a u-v path P such that G-E(P) is k-connected for any pair of
vertices u and v.
This is joint work with Ken Kawarabayashi, Orlando Lee, and Bruce Reed.