Colloquium
4:00 p.m., Monday (February 27, 2006)
MATH 105
Shakhar Smorodinsky
Courant Institute of Mathematical Sciences
Coloring Geometric Hypergraphs
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.
Refreshments will be served at 3:45 p.m. (MATX 1115, Math Lounge).
|