The Library
Independence number and the complexity of families of sets
Tools
UNSPECIFIED (1996) Independence number and the complexity of families of sets. DISCRETE MATHEMATICS, 154 (1-3). pp. 203-216. ISSN 0012-365X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Independence number (IN) is associated with a collection of sets. It is the maximum size of a subcollection such that all intersections of members or complements of members, that is all elementary sets, from the subcollection are nonempty. This paper develops the theory and gives examples of exact and asymptotic evaluations. The asymptotic results are as the dimension d of the space goes to infinity. There is a close link to Vapnik-Chernovenkis dimension and complexity issues in computational geometry. In one common case the IN is equal to the VC dimension and the fact that the so-called growth functions are the same gives improvements over Sauer's Lemma for several examples. A point-set duality also establishes a link which gives a version of Sauer's lemma for the IN. The IN controls the depth of inclusion-exclusion identities for the collection of sets with application to probability identities.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Journal or Publication Title: | DISCRETE MATHEMATICS | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0012-365X | ||||
Official Date: | 15 June 1996 | ||||
Dates: |
|
||||
Volume: | 154 | ||||
Number: | 1-3 | ||||
Number of Pages: | 14 | ||||
Page Range: | pp. 203-216 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |