Shattering, graph orientations, and connectivity
From MaRDI portal
(Redirected from Publication:396883)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3172312 (Why is no real title available?)
- scientific article; zbMATH DE number 3487496 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1113985 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 2053394 (Why is no real title available?)
- scientific article; zbMATH DE number 841577 (Why is no real title available?)
- scientific article; zbMATH DE number 3257176 (Why is no real title available?)
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A note on counting orientations
- A note on k-strongly connected orientations of an undirected graph
- Active learning
- Active learning using smooth relative regret approximations with applications
- Algorithms for the Generalized Sorting Problem
- Combinatorics of lopsided sets
- Defect Sauer results
- Digraphs. Theory, algorithms and applications
- Distances in orientations of graphs
- Embeddings and the trace of finite sets
- General percolation and random graphs
- Lopsided sets and orthant-intersection by convex sets
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the density of families of sets
- On the orientation of graphs
- Shattering news
- Some combinatorial applications of Gröbner bases
- The k -Connectedness of Unlabelled Graphs
- The acyclic orientation game on random graphs
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The number of oriantations having no fixed tournament
- Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
Cited in
(13)- Shattering-extremal set systems from Sperner families
- On partial cubes, well-graded families and their duals with some applications in graphs
- Min-cost-flow preserving bijection between subgraphs and orientations
- Counting H-free orientations of graphs
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- scientific article; zbMATH DE number 5304947 (Why is no real title available?)
- 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
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)
