Speaker: Shakhar Smorodinsky

Title: New trends in geometric hypergraph coloring

We survey two hypergraph coloring notions and focus on
hypergraphs that arise in geometry and their applications.


Polychromatic coloring:
We study questions of the following nature: is it true that there
exists a constant $f=f(k)$ such that any finite set $P$ in
${\mathbb R}^2$ can be colored using $k$ colors such that every
axis-parallel square containing at least $f(k)$ points also
contains a point from each color class? If the answer is
affirmative, obtain sharp bounds for the minimum such $f(k)$. Such
problems are related to several known notions such as {\em cover
decomposable} sets, first studied by J. Pach. The question is
whether for a given convex body $Q$ there exists a constant $f$
such that every family, which form an $f$-fold covering of the
plane with translates of $Q$, can be decomposed into two disjoint
($1$-fold) coverings? It is also related to the notions of
geometric discrepancy and of $\epsilon$-nets. Motivation also
arise in sensor networks.

Conflict-Free coloring:
Given a hypergraph $H=(V,\cal E)$, a coloring of its vertices is
said to be conflict-free if for every hyperedge $S \in \cal E$
there is at least one vertex whose color is distinct from the
colors of all other vertices in $S$. This notion is motivated by
frequency assignment problems in wireless networks and activation
protocol in RFID networks.