July 9, 2007
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
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
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.