✦ LIBER ✦

Sperner families of bounded VC-dimension

✍ Scribed by R.P. Anstee; A. Sali

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 344 KB
Volume: 175
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00137-9

No coin nor oath required. For personal study only.

✦ Synopsis

We explore a problem of Frankl (1989). A family ~ of subsets of {1, 2, ..., m} is said to have trace Kk if there is a subset SC_{1,2 ..... m} with IS] = k so that {FNSIF C .~} yields all 2 k possible subsets. Frankl (1989) conjectured that a family ~ which is an antichain (in poser given by C_ order) and has no trace Kk has maximum size (k~l) for m > 2k -4 and we verify this for k = 4 by finding the extremal families for k = 2, 3. We are attempting to bring together Spemer's theorem and the results of Vapnik and Chervonenkis (1971), Sauer (1972), Perles and Shelah (1972). We also consider the function f(m, k, l), whose value was conjectured by Frankl (1989), which is the maximum size of ,~-with no trace equal to Kk and no chain of size l + 1. We compute f(m,k,k -1) and for f(m,k,k) provide an unexpected construction for extremal families achieving the bound.

📜 SIMILAR VOLUMES

The VC-Dimension of Sperner Systems

✍ G. Greco 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 119 KB

A family F of subsets of a finite set X shatters a set D X, if the intersections of the members of F with D coincide with the power set of D. The maximum size of a set shattered by F is the VC-dimension (or density) of the system. P. Frankl (1983, J. Combin. Theory Ser. A 34, 41 45) investigates the

Exact VC-dimension of Boolean monomials

✍ Thomas Natschläger; Michael Schmitt 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 166 KB

Polynomial Bounds for VC Dimension of Si

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks

✍ Marek Karpinski; Angus Macintyre 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 438 KB

We introduce a new method for proving explicit upper bounds on the VC dimension of general functional basis networks and prove as an application, for the first time, that the VC dimension of analog neural networks with the sigmoidal activation function \_( y)=1Â1+e & y is bounded by a quadratic poly

On the complexity of approximating the V

On the complexity of approximating the VC dimension

✍ Elchanan Mossel; Christopher Umans 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: 3 -hard to approximate to within a factor 2 À e for all e > 0; \* approximable in AM to within a factor 2; and \* AM-hard to appr

A Lower Bound for Families of Natarajan

A Lower Bound for Families of Natarajan Dimension d

✍ Paul Fischer; Jiřı́ Matoušek 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 98 KB

A system F of functions [1, 2, ..., n] Ä [1, 2, ..., k] has Natarajan dimension at most d if no (d+1)-element subset A/X is 2-shattered. A is 2-shattered if for each x # A there is a 2-element set V x [1, 2, ..., k] such that for any choice of elements c x # V x , a function f # F exists with f (x)=

Families of chains of a poset and Sperne

Families of chains of a poset and Sperner properties

✍ Bruno Leclerc 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 626 KB

A subset A of a poset P is a q-anti&in if it can be obtained as the union of at most q antichains. A ranked poset P is said to be q-Sperner if the maximum number of elements of a q-antichain of P is the sum of the cardinalities of its q larger rank-sets. P is strongly Spernu if it is q-Sperner for a