The potential to improve the choice

The Faculty of Informatics is pleased to announce a seminar given by Panagiotis Cheilaris

DATE: Thursday, April 21st 2011
PLACE: USI Università della Svizzera italiana, room SI-003, Informatics building (Via G. Buffi 13)
TIME: 10.30

ABSTRACT:
Given a hypergraph H=(V,E), a vertex coloring C:V->IN is said to be unique-maximum (um for short) if for every hyperedge S in E, the maximum color occurring in S, i.e. max{C(v)|v in S}, occurs in exactly one vertex of S. Um-coloring has several applications, e.g., in frequency assignment in cellular networks.

We study the list version of um-coloring.
Given is a hypergraph H=(V,E) and a family L of |V| lists of colors, where each vertex in V is associated with a list.
We denote the list associated with v by L(v).
We say that hypergraph H admits a um-coloring from family L if there exists a um-coloring C such that C(v) in L(v).
Intuitively, v can only be colored with colors from its list L(v).
The minimum integer x such that
"for any family L with |L(v)| >= x for every v in V, H admits a um-coloring from L"
is called the um-choice number of H and is denoted by chum(H).

We prove that if a hypergraph H with n vertices is hereditarily k-colorable (in the classic non-monochromatic sense), where k is a constant, then chum(H) = O(logn) and this bound is asymptotically tight. The proof is constructive and uses a suitable potential function for constructing a um-coloring and analyzing the size of lists needed. As a corollary, we get algorithms for um-coloring hypergraphs induced by geometric shapes, given lists of logarithmic size.

Joint work with Shakhar Smorodinsky and Marek Sulovský.

BIO:
Panagiotis Cheilaris studied at the School of Electrical and Computer Engineering of the National Technical University of Athens and received his doctoral degree in Computer Science from the City University of New York, in 2008. He worked as a postdoctoral research fellow at the Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, in the first half of 2009. Since fall 2009, he is a postdoctoral research fellow at the Center for Advanced Studies in Mathematics, Ben-Gurion University of the Negev, Israel.

HOST: Prof. Evanthia Papadopoulou