Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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