The VC-dimension of K-vertex D-polytopes

DOI10.1007/S00493-020-4475-4zbMATH Open1474.52017arXiv2004.04841OpenAlexW3106546233MaRDI QIDQ2663418FDOQ2663418

Authors: Andrey B. Kupavskii 

Publication date: 16 April 2021

Published in: Combinatorica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Learnability and the Vapnik-Chervonenkis dimension
• Title not available (Why is that?)
• On the Betti Numbers of Real Varieties
• Title not available (Why is that?)
• Tight lower bounds on the VC-dimension of geometric set systems

Cited In (4)

• The VC dimension of k‐uniform random hypergraphs
• Active-learning a convex body in low dimensions
• 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)