### DIMACS Theoretical Computer Science Seminar

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.