Combinatorics Seminar

When: Sunday, April 3, 10am Where: Schreiber 309 Speaker: Nicolas Bousquet, U. Montpellier Title: VC-dimension and the Erdos-Posa property

Abstract:

The Vapnik-Chervonenkis dimension of a hypergraph H (or VC-dimension for short) is a measure of complexity of the hypergraph. Indeed, a hypergraph has its transversality bounded by a function of its VC-dimension and its fractional relaxation of the transversality. A natural way to consider a graph is to consider its hypergraph of neighborhoods. This can, for example, give us some properties on dominating sets for the graph. In this talk we will make a short survey of the use of VC-dimension and then we will propose a definition of VC-dimension for graphs and prove that the transversality can be bounded by a function of the packing number and the VC-dimension (such a property is called the Erdos-Posa property).