CS 298-2
Theory Seminar

Shakhar Smorodinsky
Courant Institute, NYU

Coloring Geometric Hypergraphs

Monday, March 6, 2006
4pm-5pm
The Wozniak Lounge, on the fourth floor of Soda Hall



Given a hypergraph H=(V,E), its conflict-free chromatic number
(CF-chromatic number) is the minimum number of colors needed to color
the vertex set V such that, for every hyperedge S, there is at least
one element v \in S whose color is unique (in S). Note that the
CF-chromatic number of a hypergraph H is at least its chromatic number
(where each hyperedge of size at least two is required to be
non-monochromatic), and at most the colorful chromatic number (where
each hyperedge is required to be colorful). I will survey some recent
results on the conflict-free chromatic number of hypergraphs that
arise from certain geometric instances and also present open problems
for further research. This ``new" coloring problem is related to the
problem of frequency assignment to cellular antennas and also time
slot assignments in RFID protocols.

(Note: the speaker does not encourage individuals to color antennas)