The VC-dimension of K-vertex D-polytopes

DOI10.1007/S00493-020-4475-4MaRDI QIDQ2663418zbMATH OpenOpenAlexFDO

Authors Andrey B. Kupavskii

Publication date 16 April 2021

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

sign patternpolytopesVC-dimensionRadon's theoremold question of Long and Warmuth

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computational aspects related to convexity (52B55)

Abstract: In this short note, we show that the VC-dimension of the class of $k$-vertex polytopes in $mathbb{R}^d$ is at most $8d^{2}klo{g}_{2}k$, answering an old question of Long and Warmuth.

Recommendations

• VC dimension and a union theorem for set systems
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• The VC-dimension of Sperner systems
• The VC dimension of k‐uniform random hypergraphs
• The Vapnik-Chervonenkis dimension of a random graph

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3053541 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• On the Betti Numbers of Real Varieties
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Tight lower bounds on the VC-dimension of geometric set systems

Cited in

(5)

• The VC dimension of k‐uniform random hypergraphs
• Active-learning a convex body in low dimensions
• On the VC-dimension of half-spaces with respect to convex sets
• The VC-dimension of axis-parallel boxes on the torus
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements

This page was built for publication: The VC-dimension of K-vertex D-polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663418)