
Discrete Mathematics and Optimization Seminar

Jan 13th, 2011 Burnside 920, 4:00 PM
Coloring via VapnikCervonenkis Dimension
Stephan Thomasse
Montpelier

Abstract: The VapnikCervonenkis 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 VCdimension, a generalization
of VCdimension to setsystems endowed with a graph structure,
hence a collection of pairs of subsets.
The classical VCtheory is generally
used in combinatorics to bound the transversality
of a hypergraph in terms of its fractional transversality
and its VCdimension. Similarly, we
bound the chromatic number of a graph
in terms of its fractional domination and its paired VCdimension.
This approach turns out to be very useful for a class of problems raised
by Erdos and Simonovits asking for
Hfree 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 VCtheory directly implies that trianglefree
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 VCdimension, we prove that the chromatic number of
Hfree 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 VCdimension. The only if is derived
from the BorsukUlam
theorem.
This is joint work with T. Lucsak.



