Shattering, graph orientations, and connectivity

zbMath1298.05145arXiv1211.1319MaRDI QIDQ396883

László Kozma, Shay Moran

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.1319

zbMATH Keywords

shatteringVC-dimensionconnectivityorientationsSauer lemma

Mathematics Subject Classification ID

Extremal set theory (05D05) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (12)

Unlabeled sample compression schemes and corner peelings for ample and maximum classes ⋮ Counting H-free orientations of graphs ⋮ Two results about the hypercube ⋮ Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Shattering-extremal set systems of VC dimension at most 2 ⋮ Standard monomials and extremal point sets ⋮ On the number of forests and connected spanning subgraphs ⋮ Shattering-extremal set systems from Sperner families ⋮ Labeled Compression Schemes for Extremal Classes ⋮ Covers, orientations and factors ⋮ Min-cost-flow preserving bijection between subgraphs and orientations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embeddings and the trace of finite sets
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• On the orientation of graphs
• Lopsided sets and orthant-intersection by convex sets
• A note on k-strongly connected orientations of an undirected graph
• Distances in orientations of graphs
• Shattering news
• Defect Sauer results
• Combinatorics of lopsided sets
• The number of oriantations having no fixed tournament
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• A note on counting orientations
• Active Learning
• Some Combinatorial Applications of Gröbner Bases
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• General percolation and random graphs
• The k -Connectedness of Unlabelled Graphs
• The acyclic orientation game on random graphs
• Algorithms for the Generalized Sorting Problem
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Spectral Theory and Analysis
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

This page was built for publication: Shattering, graph orientations, and connectivity