Visual Cryptography and Contrast Bounds - Visual Cryptography and Secret Image Sharing - page 223

It is convenient to replace the size of the sets in the approximated inclusion
exclusion problem by arbitrary measures to get a continuous problem. This
leads to the following problem. Let (;A;) be a measurable space and let
A 1 ;:::;A n and B 1 ;:::;B n be measurable sets with

\ \

A i = B i

i2S i2S

for every subset S f1;:::;ng such that jSj < m, what is the smallest (or
largest) possible value for the fraction

(A 1 [:::[A n )
(B 1 [:::[B n ) ?

Similarly to Lemma 1 we can restrict the approximate inclusion-exclusion
problem to symmetric collections. With

2
4

3
5

n
j

\ \

A j \ \
j2S

B j \ \
j2S

x i = A j B j

j2S j2S

for jSj = i the approximate inclusion-exclusion problem leads to the linear
program

X

Maximize: x i (8.6)

i=1

subject to:

i
j

X

x i = 0 for 1 j < m (8.7)

i=j

1 X
i2S

x i 1 for allS f1;:::;ng : (8.8)

(See [15] Lemma 3 for a proof).
Dualizing the linear program leads to the following problem of approxima-
tion theory (see [15] Lemma 5 and Section 8.6 where we use that technique
to determine the asymptotic behavior of k-out-of-n schemes).
Determine

inf
q x=1;:::;n 1 q(x)

max (8.9)

where the infimum ranges over all polynomials q of less than m that have zero
constant terms and satises q(x) 1 for all x 2f1;:::;ng.
The special case m = n leads to Krawtchuck polynomials (see [15] The-
orem 3). But for this special case a elementary combinatorial proof exists
(see [12]).