Next: An Application: Ramsey Graphs Up: Superpolynomial Size Set-Systems with Previous: Preliminaries

# The Lower Bound

Proof of Theorem 1.2.

Let 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.

Let Q(z1,z2,...,zn)=P(1-z1,1-z2,....,1-zn). Then , and for all we have

Using the polynomial Q we state our main Lemma:

Lemma 3.1   For every integer n>0, there exists a uniform set-system over a universe of 2(m-1)n2d/d! elements which is explicitly constructible from the polynomial Q and satisfies
(a)
,
(b)
,
(c)
.

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

where , and is integer, . Let us define

where is the smallest, positive integer, congruent to modulo m, for .

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 is permutationally equivalent to the matrix

where the diagonal blocks Ji are all-ones matrices of size , and there are exactly pairwise disjoint all-ones blocks in . Permutationally equivalent'' means that there exists a permutation such that if it is applied both to the rows and to the columns of the matrix, the result is equal to (6). Let us refer to these all-ones blocks of as B-blocks. We shall say that each B-block of occurs with multiplicity .

By equation (4), A can be written in the following form:

Lemma 3.2   Taking multiplicities into account,
(a)
every cell of the main diagonal of A is covered by the same number of B-blocks, and this number is divisible by m;
(b)
for any pair of cells of the main diagonal of A, the number of those B-blocks which cover both members of the pair, is not divisible by m.

Proof. 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).

Corollary 3.3   There exists an explicitly constructible hypergraph with nn vertices and fewer than 2(m-1)n2d/d! edges, such that every vertex is contained in the same number of edges, and this number is divisible by m; while for any two vertices, the number of edges, containing both of the vertices, is not divisible by m. (We allow multiple edges and take multiplicities into account.)

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

assuming, as we may, that .

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.

Remark 3.4   We note from the foregoing that the number of vertices of is , and the number of vertices of each member of is . We note that

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

and therefore the size of the members of is

as claimed in equation (2).

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.

Next: An Application: Ramsey Graphs Up: Superpolynomial Size Set-Systems with Previous: Preliminaries
Vince Grolmusz
1999-11-08