Discrete Mathematics and Optimization Seminar
Jan 13th, 2011 |
Burnside 920, 4:00 PM
Coloring via Vapnik-Cervonenkis Dimension
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
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
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
the minimum degree is cn, with c<1/3.
Using paired VC-dimension, we prove that the chromatic number of
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
This is joint work with T. Lucsak.