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

shattering; VC-dimension; connectivity; orientations; Sauer lemma

Mathematics Subject Classification ID

05D05: Extremal set theory

05C20: Directed graphs (digraphs), tournaments

05C40: Connectivity

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item