ColloquiaTalk by Michael Langberg - Monday, November 4, 2002

[Margery Ishmael]

-----------------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE

Monday, November 4, 2002 at 2:30 p.m. in Ryerson 251

----------------------------------------------------------------------------------- 


Speaker: MICHAEL LANGBERG, Weizmann Institute of Science, Israel

Title: "Graphs with tiny vector chromatic numbers and huge chromatic numbers"

Abstract: Karger, Motwani and Sudan (JACM 1998) introduced the notion of a 
vector
coloring of a graph. In particular they show that every $k$-colorable graph 
is also vector $k$-colorable, and that for constant $k$, graphs that are 
vector $k$-colorable can be colored by roughly $\Delta^{1 - 2/k}$ colors. 
Here $\Delta$ is the maximum degree in the graph. Their results
play a major role in the best approximation algorithms for coloring and for 
maximal independent set.

We show that for every positive integer $k$ there are graphs that are 
vector $k$-colorable but do not have independent sets significantly larger 
than $n/\Delta^{1 - 2/k}$ (and hence cannot be colored with significantly 
less that $\Delta^{1 - 2/k}$ colors). For $k = O(\log n/\log\log n)$ we
show vector $k$-colorable graphs that do not have independent sets of size 
$(\log n)^c$, for some constant $c$. This shows that the vector chromatic 
number does not approximate the chromatic number within factors better than 
$n/{\mbox{polylog}} n$. As part of our proof, we analyze ``property 
testing'' algorithms that distinguish between graphs that have an 
independent set of size $n/k$, and graphs that are ``far'' from having such 
an independent set. Our bounds on the sample size improve previous bounds 
of Goldreich, Goldwasser and Ron (JACM 1998) for this problem. 
www.wisdom.weizmann.ac.il/~mikel/   Joint work with U. Feige and G. Schechtman.

HOST: Janos Simon

*The talk will be followed by refreshments in Ryerson 255*

If you would like to meet with the speaker, please send e-mail to 
marge at cs.uchicago.edu
Persons who need assistance should call 773.834.8977