When: Sunday, February 23, 10am
Where: Schreiber 309
Speaker: Shay Moran, Technion
Title: Shattering and Graph Orientations
Consider the following puzzles:
1.[A-cylic orientations] Let G be a simple undirected graph. Show that the number of orientations of G which gives a Directed Acyclic Graph is at most the number of spanning sub-forests of G (= spanning subgraphs of G that are forests).
2.[Strong orientations] Robbin's Theorem states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. Prove that for every graph G, the number of strong orientations of G is at least the number of 2-edge-connected spanning subgraphs of G and at most the number of connected spanning subgraphs of G.
In this talk I will present a unified approach which gives simple proofs for the above inequalities and many other inequalities of this flavor. The approach is based on a connection between two seemingly disparate fields: VC-theory and graph theory. This connection yields natural correspondences between fundamental concepts in VC-theory, such as shattering and VC-dimension, and well-studied concepts of graph theory related to connectivity, combinatorial optimization, forbidden subgraphs, and others. The main tool is a generalization of the Sauer-Shelah Lemma [Pajor 85, Bollobas and Radcliffe 95, Dress 97,...]. Using this tool we obtain a series of inequalities and equalities related to properties of orientations of a graph.
The talk will be based on the following papers: Shattering Extremal Systems [S. Moran] http://arxiv.org/abs/1211.2980
Shattering, Graph Orientations and Connectivity [L. Kozma, S. Moran] http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p44