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).

Copyright © 2006 UBC Mathematics Department