Shattering, graph orientations, and connectivity
From MaRDI portal
Publication:396883
zbMATH Open1298.05145arXiv1211.1319MaRDI QIDQ396883FDOQ396883
Authors: László Kozma, Shay Moran 
Publication date: 14 August 2014
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Abstract: We present 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. In one direction, we use this connection to derive results in graph theory. Our main tool is a generalization of the Sauer-Shelah Lemma. Using this tool we obtain a series of inequalities and equalities related to properties of orientations of a graph. Some of these results appear to be new, for others we give new and simple proofs. In the other direction, we present new illustrative examples of shattering-extremal systems - a class of set-systems in VC-theory whose understanding is considered by some authors to be incomplete. These examples are derived from properties of orientations related to distances and flows in networks.
Full work available at URL: https://arxiv.org/abs/1211.1319
File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)
Recommendations
Cites Work
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Shattering news
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Title not available (Why is that?)
- Digraphs. Theory, algorithms and applications
- Title not available (Why is that?)
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- Defect Sauer results
- Embeddings and the trace of finite sets
- Distances in orientations of graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
- On the orientation of graphs
- Lopsided sets and orthant-intersection by convex sets
- A note on k-strongly connected orientations of an undirected graph
- Combinatorics of lopsided sets
- The number of oriantations having no fixed tournament
- A note on counting orientations
- Active learning
- Active learning using smooth relative regret approximations with applications
- Some combinatorial applications of Gröbner bases
- General percolation and random graphs
- The k -Connectedness of Unlabelled Graphs
- Title not available (Why is that?)
- The acyclic orientation game on random graphs
- Algorithms for the Generalized Sorting Problem
Cited In (13)
- Counting H-free orientations of graphs
- Min-cost-flow preserving bijection between subgraphs and orientations
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Title not available (Why is that?)
- Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
- On the number of forests and connected spanning subgraphs
- Shattering-extremal set systems of VC dimension at most 2
- Covers, orientations and factors
- Standard monomials and extremal point sets
- Two results about the hypercube
- Labeled compression schemes for extremal classes
- Shattering-extremal set systems from Sperner families
- On partial cubes, well-graded families and their duals with some applications in graphs
This page was built for publication: Shattering, graph orientations, and connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396883)
