**Monday, May 4, 2009**

Technische Universität Berlin

Fak. II, Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

room MA 041

** Lecture - 14:15**

*Abstract:*

It is shown that, for any $\epsilon > 0$, every graph of
maximum degree $\Delta$ permits a {\em conflict-free
coloring} with at most $\log^{2+\epsilon}\Delta$ colors,
that is, a coloring with the property that the neighborhood
$N(v)$ of any vertex $v$, contains an element whose color
differs from the color of any other element of $N(v)$. We
give an efficient deterministic algorithm to find such a
coloring, based on an algorithmic version of the Lov\'asz
Local Lemma suggested by Beck, Molloy and Reed. We need to
correct a small error in the Molloy-Reed approach, restate
it in a deterministic form, and re-prove it

The problem can be extended to arbitrary hypergraphs $H$: a
coloring of the vertices of $H$ is called
{\em conflict-free} if each hyperedge $E$ of $H$ contains a
vertex whose color does not get repeated in $E$. Every
hypergraph with fewer than ${s \choose 2}$ edges permits a
conflict-free coloring with fewer than $s$ colors, and this
bound cannot be improved. Moreover, there is a linear time
deterministic algorithm for finding such a coloring.
The concept of conflict-free colorings was first raised in a
geometric setting in connection with frequency assignment
problems for cellular networks.

Joint work with G\'abor Tardos.

** Colloquium - 16:00 **

*Abstract:*

In addition to approximation algorithms, parameterized complexity theory is a well-known approach when dealing with NP-hard (optimization) problems. The central definition of fixed parameter tractability expresses that the corresponding decision problem can be solved in time O(f(k)n^c), where k is the parameter, e.g., the size of the solution, c is a constant independent of k, and f is an arbitrary computable function. Only recently, one has begun to apply this theory to a geometric context.

In this talk, we will analyze several variants of geometric stabbing problems from a parameterized complexity point of view. In particular, we will show that the problem of stabbing unit-squares with lines does not allow an fpt algorithm when parameterized with the size of the solution (under standard complexity-theoretic assumptions). Still, we will consider some restrictions of the general problem for which such algorithms can be found. Finally, several open problems that arise from geometric settings are presented.

*Abstract:*

For a graph $G$ and $d\in \mathbb N,$ the $d$-girth $g_d(G)$ of $G$ is the minimum order of an induced subgraph of $G$ of minimum degree at least $d$ (or $\infty,$ if no such subgraph exists). The $2$-girth of a graph is the same as its usual girth (the length of a shortest cycle), so the $d$-girth is a generalization of the girth. In particular, we examine the $(d+k)$-girth of $C_n^d,$ the $d$-th power of a cycle of length $n.$ This is motivated by a conjecture of K{\'e}zdy and Markert, that $C_n^d$ are the $2d$-regular graphs with largest $(d+1)$-girth. In 1989 Bermond and Peyrat proved $g_{d+k}(C_n^d)\geq \frac{d+k}{2d}$
for $1\leq k\leq d$ which is best-possible for even $d+k,$ but not for odd $d+k.$ In order to improve these results, we reduced the problem of computing $g(d,k):=\inf \left\{ g_{d+k}(C_n^d)/n ~|~n\geq 3 \right\}$ to a minimum mean cycle problem. From the obtained data, we could conclude a general conjecture concerning the $(d+k)$-girth of $C_n^d$ for odd values of $d+k.$ We proved this conjecture for $k=d-3.$

Letzte Aktualisierung:
28.04.2009