UNSPECIFIED (1996) Independence number and the complexity of families of sets. DISCRETE MATHEMATICS, 154 (1-3). pp. 203-216. ISSN 0012-365X

Full text not available from this repository.

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
Date:	15 June 1996
Volume:	154
Number:	1-3
Number of Pages:	14
Page Range:	pp. 203-216
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/18619

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item