Authors
Citation
Sj. Szarek et M. Talagrand, ON THE CONVEXIFIED SAUER-SHELAH THEOREM, J COMB TH B, 69(2), 1997, pp. 183-192
Citations number
7
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
69
Issue
2
Year of publication
1997
Pages
183 - 192
Database
ISI
SICI code
0095-8956(1997)69:2<183:OTCST>2.0.ZU;2-L
Abstract
Let A be a subset of {0, 1}(n). Given epsilon > 0, we can find a subse
t I of {I, ..., n} such that the convex hull in R(I) of the projection
of A onto {0, 1}(I) contains the cube [1/2 - epsilon, 1/2 + epsilon](
I), and that card I greater than or equal to n - K(n epsilon + root n
log(2(n)/card A)), where K > 0 is a universal constant. (C) 1997 Acade
mic Press.