Proof of Theorem 1.2.
P(z1,z2,...,zn) be a polynomial of degree d
which satisfies that
and for every
An explicit construction of such P of degree d=O(n1/r) was given in Theorem 2.2.
and for all
Using the polynomial Q we state our main Lemma:
Lemma 3.1 easily yields Theorem 1.2 setting and using elementary estimations for the binomial coefficients.
Proof of Lemma 3.1. Q can be written as
We note, that (3) is satisfied for , but is not necessarily 0.
Let the function
be defined as
Let A=(axy) be an nn x nn matrix ( ).
We define the entry axy as follows:
We note that . Conversely, if then x=y.
By equation (4), the polynomial is a sum of the monomials of the form . We wish to keep all coeffcients equal to 1; therefore we shall say that the monomial occurs with multiplicity in this sum. Note that each multiplicity is a nonnegative integer .
Consequently, the matrix A is a sum of the matrices , corresponding to the monomial in the following way:
This matrix occurs in the sum with multiplicity .
It is easy to verify that
equivalent to the matrix
By equation (4), A can be written in the following form:
We note that the number of B-blocks covering cell (x,y) is axy.
Now statement (a) follows by equation (3), observing that for all x,
For part (b), we note that the B-blocks are square submatrices, symmetric to the diagonal; therefore a B-block covers the cells (x,x) and (y,y) exactly if it covers the cell (x,y). The number of B-blocks covering both (x,x) and (y,y) is therefore , again by equation (3).
Proof. From Lemma 3.2, choose the cells of the diagonal of A for the vertices and the intersections of the B-blocks with the diagonal for edges (with the corresponding multiplicity).
The number of edges is
We note that the number of edges containing each vertex is
Now we are ready to complete the proof of Lemma 3.1.
Let us consider the dual of the hypergraph of Corollary 3.3, i.e., let the universe be the set of B-blocks, and if a B-block was present a times in the hypergraph , then it will correspond to a different points (or elements) in the universe. Consequently, our universe is a set (rather than a multiset). The size of the universe is h < 2(m-1)n2d/d!.
The diagonal cells of A correspond to the members of the set-system : the set corresponding to cell (x,x) consists of exactly those B-blocks which cover (x,x). Therefore
Since every diagonal cell of A is covered by the same number of B-blocks, the resulting is a uniform set system. As discussed previously, this number (the size of the members of ) is .
From Corollary 3.3, statements (a), (b), (c) of Lemma 3.1 follow.
To prove the estimate on the size of the members of in terms of h (the number of vertices of ) given in Remark 1.3, we first add dummy vertices to increase h to its upper bound stated above. Now, since this quantity is still , we see, using the bound d=O(n1/r) guaranteed by Theorem 2.2, that
Proof of Theorem 1.4. The statement is immediate if the polynomial P' of Corollary 2.4 is used for the construction of the set-system in the proof of Theorem 1.2 in the place of the polynomial P.
Proof of Corollary 1.6 Let , and apply Theorem 1.4 for constructing a set-system for h and this m'. The intersections occupy only 3 residue classes modulo m'. Now replace every point of the universe by m/m' new points; the new points will be the members of exactly the same sets of the set-system as the old point. The statement follows.