Monday, January 10, 2011
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
Lecture - 14:15
Abstract:
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
Abstract:
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.