Independence number and the complexity of families of sets
UNSPECIFIED (1996) Independence number and the complexity of families of sets. DISCRETE MATHEMATICS, 154 (1-3). pp. 203-216. ISSN 0012-365XFull text not available from this repository.
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|
|Date:||15 June 1996|
|Number of Pages:||14|
|Page Range:||pp. 203-216|
Actions (login required)