Discrete Mathematics and Optimization Seminar
Jan 13th, 2011
Burnside 920, 4:00 PM
Coloring via Vapnik-Cervonenkis Dimension
Stephan Thomasse
Abstract: The Vapnik-Cervonenkis dimension is a complexity measure of hypergraphs. Its application to graphs is usually done by considering their neighborhood hypergraph. But the graph structure is lost in the process. The aim of this paper is to introduce the notion of paired VC-dimension, a generalization of VC-dimension to set-systems endowed with a graph structure, hence a collection of pairs of subsets.

The classical VC-theory is generally used in combinatorics to bound the transversality of a hypergraph in terms of its fractional transversality and its VC-dimension. Similarly, we bound the chromatic number of a graph in terms of its fractional domination and its paired VC-dimension.

This approach turns out to be very useful for a class of problems raised by Erdos and Simonovits asking for H-free graphs with minimum degree at least cn and arbitrarily high chromatic number, where H is a fixed graph, c is a positive constant, and n is the number of vertices.

We first show how the usual VC-theory directly implies that triangle-free graphs with minimum degree at least n/3 have chromatic number at most 1665. Note that by a construction of Hajnal, the chromatic number is unbounded when the minimum degree is cn, with c<1/3.

Using paired VC-dimension, we prove that the chromatic number of H-free graphs with minimum degree at least cn is bounded for every choice of c>0 if and only if H has a stable set which intersect every odd cycle at least twice.

The if part follows from our paired VC-dimension. The only if is derived from the Borsuk-Ulam theorem.

This is joint work with T. Lucsak.