MathDB

Given is a set

A

n

elements and positive integers

k, m

such that

4 \leq k <n

and

m \leq \min \{k-3, \frac {n} {2}\}

. Let

A_1, A_2, \ldots, A_l

be subsets of

A

, all with size

k

, such that

|A_i \cap A_j| \leq m

for all

i \neq j

. Prove that there exists a subset

B

A

with at least

\sqrt[m+1]{n}+m

elements which doesn't contain entirely any of the subsets

A_1, A_2, \ldots, A_l

Problem Statement