Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, January 31, 2006 - 4:00pm

Shakhar Smorodinsky

New York University

Location

University of Pennsylvania

DRL 4E19

Please note change from usual room

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.