# Combinatorics Seminar

When: Sunday, February 23, 10am

Where: Schreiber 309

Speaker: Shay Moran, Technion

Title: Shattering and Graph Orientations

## Abstract:

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

redesigned by barak soreq