𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Aq-Analog of Approximate Inclusion–Exclusion

✍ Scribed by Marios Mavronicolas

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
223 KB
Volume
20
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the lattice of subspaces of an n-dimensional vector space V n over a q Ž . 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 V n in terms of the sizes of subsets of q X whose intersection contains a given subspace of V n . We study the problem of q ' ' of approximation changes in a significant way around q

'

then any approximation may err by a factor of ⌰ q rk ; while if k G ny 1 Ž .

'

⍀ q , the size of the union may be approximated to within a multiplicative

factor of 1 q e . 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.

📜 SIMILAR VOLUMES

A note on approximate inclusion-exclusio
A note on approximate inclusion-exclusion
✍ Avraham A Melkman; Solomon E Shimony 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 190 KB

Let A,, i = I,. ,n, be a sequence of sets, and for S C[r?] set as := 1 fl,,.~ A,I.

q-Analogs of the inclusion- exclusion pr
q-Analogs of the inclusion- exclusion principle and permutations with restricted position
✍ William Y.C. Chen; Gian-Carlo Rota 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 946 KB

We derive a q-analog of the principle of inclusion-exclusion, and use it to derive a q-analog of the Kaplansky-Riordan theory of permutations with restricted position. Some analogies with the theory of Mahonian statistics are pointed out at the end, leading to a conjectured relationship between the