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 conflictfree chromatic number
(CFchromatic 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 CFchromatic number of a hypergraph H is at least
its chromatic number (where each hyperedge of size at least
two is required to be nonmonochromatic), and at most
the colorful chromatic number (where each hyperedge is required
to be colorful).
I will survey some recent results on the conflictfree
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).
