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

Janos Pach - EPFL Lausanne and CUNY New York

Conflict-free colorings of graphs and hypergraphs

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

Daniel Werner - FU Berlin

Fixed-parameter tractability and lower bounds for stabbing problems

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.

Janina Müttel - Berlin

On the Generalized Girth of Cycle Powers

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