A q-Analog of Approximate Inclusion-Exclusion

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.

Abstract:

We consider the lattice of subspaces of an n-dimensional vector space Vnq over a finite field GF(q) and represent a family of such subspaces by elements of a set X. The q-analog of the principle of inclusion-exclusion expresses the size of the union of elements of X representing subspaces of Vnq in terms of the sizes of subsets of X whose intersection contains a given subspace of Vnq . We study the problem of approximating the size of this union when intersection sizes are known only for some subspaces of Vnq . In particular, we consider the case where intersection sizes are given for subsets of X whose intersection contains a subspace of Vnq of dimension at most k. We extend methods of Linial and Nisan (1990, Combinatorica 10, No. 4, pp. 349-365), drawn from approximation theory, to show that the quality of approximation changes in a significant way around : if , then any approximation may err by a factor of ; while if , the size of the union may be approximated to within a multiplicative factor of . Our result, the first q-analog of a computational property of the lattice of subsets of a finite set, answers in the affirmative a question posed by Linial and Nisan. Copyright 1998 Academic Press.

Document Type: Research Article

Affiliations: Department of Computer Science, University of Cyprus, Nicosia, CY-1678, Cyprus

Publication date: January 1, 1998

Related content

Tools

Favourites

Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
X
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more