#
Monday Lecture and Colloquium

**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**

###
Yoshiharu Kohayakwa - Universidade de São Paulo

###
The size-Ramsey number

*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**

###
Paul Wollan - Universität Hamburg

### Progress on Removable Paths Conjectures

*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.

Letzte Aktualisierung:
18.06.2007