Title: Properly 2-Colouring Linear Hypergraphs
Speaker: Arkadev Chattopadhyay, McGill University
Date: Wednesday, October 22, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Using the symmetric form of the Lovasz Local Lemma, one can conclude that a k-uniform hypergraph admits a proper 2-colouring of its vertices if the maximum degree Delta is at most 2^k/8k, independent of the size of the hypergraph. However this argument does not yield an efficient algorithm to find such a colouring.
A hypergraph is called linear if no two hyperedges have more than one vertex in common. We present a deterministic polynomial time algorithm for 2-colouring every k-uniform linear hypergraph with Delta <= 2^{k-k^{epsilon}}, where 1/2 < epsilon < 1 is an arbitrary constant and k is larger than a constant that depends on epsilon.
This is joint work with Bruce Reed.