On the convexified Sauer-Shelah theorem
type: Item
instance of: scholarly article
title: On the convexified Sauer-Shelah theorem
zbMATH Open document ID: 0868.05051
author: Stanislaw J. Szarek
author: Michel Talagrand
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-06-03T00:00:00Z
review text: Let \(A\) be a subset of \(\{0,1\}^n\). Given \(\varepsilon>0\), we can find a subset \(I\) of \(\{1,\dots,n\}\) such that the convex hull in \(\mathbb{R}^I\) of the projection of \(A\) onto \(\{0,1\}^I\) contains the cube \([1/2-\varepsilon,1/2+\varepsilon]^I\), and that \(\text{card }I\geq n-K(n\varepsilon+\sqrt{n\log(2^n/\text{card }A)})\), where \(K>0\) is a universal constant.
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1006756
zbMATH Keywords: Sauer-Shelah theorem
zbMATH Keywords: combinatorial complexity
MaRDI profile type: Publication
full work available at URL: jctb.1996.1736
OpenAlex ID: W2082435672
cites work: A Remark on the Szarek–Talagrand Theorem
cites work: A proportional Dvoretzky-Rogers factorization result
cites work: Q4083487
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
cites work: Q3828516
DOI: 10.1006/JCTB.1996.1736
description: scientific article; zbMATH DE number 1006756