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

Monday, January 10, 2011

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin

Lecture - 14:15

Gabor Tardos, Budapest

Epsilon-nets for geometric range spaces

I will start with the famous theorem of Haussler and Welzl about epsilon-nets for ranges of bounded VC-dimension and explore what range spaces allow for tighter bounds on epsilon-nets. We will consider geometric range spaces consisting of half spaces, axis parallel boxes and other geometric sets and also their duals. This is a survey talk on recent results of Alon, Aronov, Ezra, Pach, Sharir and myself.

Colloquium - 16:00

Roman Glebov, Berlin

Conflict-free coloring of graphs

Conflict-free coloring can be interpreted as a relaxation of the usual {\em proper coloring} concept. We require that for each vertex $x\in V$, there is a vertex $y$ in the closed neighborhood $N[x]:= N(x)\cup \{ x\}$ of $x$ whose color is different from the color of every other vertex in $N[x]$. Similarly to the chromatic number of a graph, the {\em conflict-free chromatic number} $\chi_{CF}(G)$ is the smallest $r$, such that there exists a conflict-free $r$-coloring of $G$. We study the conflict-free chromatic number $\chi_{CF}$ of graphs from an extremal and probabilistic point of view. We resolve a question of Pach and Tardos about the maximum conflict-free chromatic number an $n$-vertex graph can have. Our construction is randomized. In relation to this we study the evolution of the conflict-free chromatic number of the Erd\H os-R\'enyi random graph $G(n,p)$. We give the asymptotics for constant and sub-constant $p$, except for the range where the conflict-free chromatic number is constant. We also show that for constant $p\geq 1/2$ the conflict-free chromatic number is within an additive constant $4$ of the domination number.
Joint work with Tibor Szabó and Gábor Tardos.

Letzte Aktualisierung: 17.12.2010