Combinatorics Seminar

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]

Shattering, Graph Orientations and Connectivity [L. Kozma, S. Moran]

w3c valid   accessible website
redesigned by barak soreq