The Vapnik-Chervonenkis dimension of a random graph

DOI10.1016/0012-365X(94)00187-NzbMath0824.05056MaRDI QIDQ1842142

Martin Anthony, Graham R. Brightwell, Colin Cooper

Publication date: 26 October 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

random graphVapnik-Chervonenkis dimensionthreshold functionclosed neighbourhoodshattered set of vertices

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Related Items

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, The VC-dimension of graphs with respect to \(k\)-connected subgraphs, The VC-dimension of set systems defined by graphs, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Constrained versions of Sauer's Lemma, Vapnik-Chervonenkis density in some theories without the independence property, I, On the VC-dimension and boolean functions with long runs

Cites Work

• \(\epsilon\)-nets and simplex range queries
• Estimation of dependences based on empirical data. Transl. from the Russian by Samuel Kotz
• Testing geometric objects
• On specifying Boolean functions by labelled examples
• Learnability and the Vapnik-Chervonenkis dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Convergence of stochastic processes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item