next up previous
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 $P(0,0,0,\ldots,0)=0$, and for every $(z_1,z_2,...,z_n)\in \{0,1\}^n$

\begin{displaymath}P(z_1,z_2,...,z_n)\equiv 0 \pmod{m} \Longleftrightarrow z_1=z_2=...=z_n=0.\end{displaymath}

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 $Q(1,1,1,\ldots,1)=0$, and for all $z\in \{0,1\}^n$ we have

\begin{displaymath}Q(z)\equiv 0\pmod{m} \Longleftrightarrow z_1=z_2=...=z_n=1.\eqno{(3)}\end{displaymath}

Using the polynomial Q we state our main Lemma:

Lemma 3.1   For every integer n>0, there exists a uniform set-system ${\cal H}$ over a universe of 2(m-1)n2d/d! elements which is explicitly constructible from the polynomial Q and satisfies
(a)
$\vert{\cal H}\vert=n^n$,
(b)
$\forall H\in {\cal H}: \ \vert H\vert\equiv0\pmod{m}$,
(c)
$\forall G, H\in {\cal H}, G\ne H: \ \vert G\cap H\vert\not\equiv0\pmod{m}$.


Lemma 3.1 easily yields Theorem 1.2 setting $d=\Theta({n^{1/r}})$ and using elementary estimations for the binomial coefficients.


Proof of Lemma 3.1. Q can be written as

\begin{displaymath}Q(z_1,z_2,...,z_n)=\sum_{i_1,i_2,...,i_\ell}a_{i_1,i_2,...,i_\ell}
z_{i_1}z_{i_2}...z_{i_\ell},\end{displaymath}

where $0\leq\ell\leq d$, and $a_{i_1,i_2,...,i_\ell}$ is integer, $1\leq i_1<i_2<\cdots<i_\ell\leq n$. Let us define

\begin{displaymath}\tilde{Q}(z_1,z_2,...,z_n)=\sum_{i_1,i_2,...,i_\ell}\tilde{a}_{i_1,i_2,...,i_\ell}
z_{i_1}z_{i_2}...z_{i_\ell},\eqno{(4)}\end{displaymath}

where $\tilde{a}_{i_1,i_2,...,i_\ell}=(a_{i_1,i_2,...,i_\ell}\bmod{m})$ is the smallest, positive integer, congruent to $a_{i_1,i_2,...,i_\ell}$ modulo m, for $1\leq i_1<i_2<\cdots<i_\ell\leq n$.

We note, that (3) is satisfied for $\tilde{Q}$, but $\tilde{Q}(1,1,1,\ldots,1)$ is not necessarily 0.


Let the function $\delta:\{0,1,...,n-1\}\times \{0,1,...,n-1\}\to \{0,1\}$ be defined as

\begin{displaymath}\delta(u,v)=\cases{1, \hbox{ if } u=v,\cr
0\hbox{ otherwise.}}\end{displaymath}

Let A=(axy) be an nn x nn matrix ( $x,y\in \{0,1,2,\ldots,n-1\}^n$).

We define the entry axy as follows:

\begin{displaymath}a_{xy}=\tilde{Q}(\delta(x_1,y_1),\delta(x_2,y_2),\ldots,\delta(x_n,y_n))\bmod{m}.\eqno{(5)}\end{displaymath}

We note that $a_{xx}= \tilde{Q}(1,1,\ldots,1)\equiv 0 \pmod m$. Conversely, if $a_{xy}\equiv 0 \pmod m$ then x=y.


By equation (4), the polynomial $\tilde{Q}(z)$ is a sum of the monomials of the form $z_{i_1}z_{i_2}...z_{i_\ell}$ $(\ell\le d)$. We wish to keep all coeffcients equal to 1; therefore we shall say that the monomial $z_{i_1}z_{i_2}...z_{i_\ell}$ $(\ell\le d)$ occurs with multiplicity $\tilde{a}_{i_1,i_2,\ldots,i_\ell}$ in this sum. Note that each multiplicity is a nonnegative integer $\le m-1$.

Consequently, the matrix A is a sum of the matrices $B_{i_1,i_2,...,i_\ell}=(b^{i_1,i_2,...,i_\ell}_{x,y})$, corresponding to the monomial $z_{i_1}z_{i_2}...z_{i_\ell}$ in the following way:


\begin{displaymath}b^{i_1,i_2,...,i_\ell}_{x,y}=\delta(x_{i_1},y_{i_1})\delta(x_{i_2},y_{i_2})
\ldots \delta(x_{i_\ell},y_{i_\ell}).\end{displaymath}

This matrix occurs in the sum with multiplicity $\tilde{a}_{i_1,i_2,\ldots,i_\ell}$.

It is easy to verify that $B_{i_1,i_2,...,i_\ell}$ is permutationally equivalent to the matrix

\begin{displaymath}\pmatrix {J_1&&& &\cr
& && \hbox{\LARGE0}&\cr
&&\ddots &&\cr
&\hbox{\LARGE0}&&&\cr
&&&&J_{n^\ell}}\eqno{(6)}\end{displaymath}

where the diagonal blocks Ji are all-ones matrices of size $n^{n-\ell}\times n^{n-\ell}$, and there are exactly $n^\ell$ pairwise disjoint all-ones blocks in $B_{i_1,i_2,...,i_\ell}$. ``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 $B_{i_1,i_2,...,i_\ell}$ as B-blocks. We shall say that each B-block of $B_{i_1,i_2,...,i_\ell}$ occurs with multiplicity $\tilde{a}_{i_1,i_2,...,i_\ell}$.

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

\begin{displaymath}A=\sum_{i_1,i_2,...,i_\ell}\tilde{a}_{i_1,i_2,...,i_\ell}
B_{i_1,i_2,...,i_\ell}.\eqno{(7)}\end{displaymath}

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,

\begin{displaymath}a_{xx}=\tilde{Q}(1,1,\ldots,1) \equiv 0 \pmod m.\end{displaymath}

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 $a_{xy}\not\equiv 0 \pmod{m}$ , again by equation (3). $\Box$

Corollary 3.3   There exists an explicitly constructible hypergraph ${\cal G}$ 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

\begin{displaymath}h:=\tilde{Q}(n,n,\ldots,n)=\sum_{\ell\le d} \sum \tilde{a}_{i...
...\ell}n^{\ell}
\le (m-1)\sum_{\ell\le d}{n\choose \ell}n^{\ell}\end{displaymath}


\begin{displaymath}< (m-1)\sum_{\ell\le d}n^{2\ell}/\ell!< 2(m-1)n^{2d}/d!,\end{displaymath}

assuming, as we may, that $n\ge 2d$. $\Box$


We note that the number of edges containing each vertex is

\begin{displaymath}\tilde{Q}(1,1,\ldots,1) \le (m-1)\left({n\choose d}+{n\choose d-1}+\ldots
{n\choose 0}\right) < 2(m-1){n\choose d}.\end{displaymath}


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 ${\cal G}$, 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 ${\cal H}$: the set corresponding to cell (x,x) consists of exactly those B-blocks which cover (x,x). Therefore $\vert{\cal H}\vert=n^n.$

Since every diagonal cell of A is covered by the same number of B-blocks, the resulting ${\cal H}$ is a uniform set system. As discussed previously, this number (the size of the members of ${\cal H}$) is $\tilde{Q}(1,1,\ldots,1) \le (m-1)\sum_{\ell=0}^d {n\choose d}
< 2(m-1){n\choose d}$.

From Corollary 3.3, statements (a), (b), (c) of Lemma 3.1 follow.$\Box$

Remark 3.4   We note from the foregoing that the number of vertices of ${\cal H}$ is $h:=\tilde{Q}(n,n,\ldots,n)$, and the number of vertices of each member of ${\cal H}$ is $\tilde{Q}(1,1,\ldots, 1)$. We note that $\tilde{Q}(n,n,\ldots,n)\le
n^d\,\tilde{Q}(1,1,\ldots,1).$


To prove the estimate on the size of the members of ${\cal H}$ in terms of h (the number of vertices of ${\cal H}$) given in Remark 1.3, we first add dummy vertices to increase h to its upper bound $h':=n^d\,\tilde{Q}(1,1,\ldots,1)$ stated above. Now, since this quantity is still $\le 2(m-1)n^{2d}/d!$, we see, using the bound d=O(n1/r) guaranteed by Theorem 2.2, that

\begin{displaymath}n^d \ge (h')^{{r\over 2r-1}+o(1)}\end{displaymath}

and therefore the size of the members of ${\cal H}$ is

\begin{displaymath}\tilde{Q}(1,1,\ldots,1) \le (h')^{{r-1 \over 2r-1}+o(1)},\end{displaymath}

as claimed in equation (2). $\Box$


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 ${\cal H}$ in the proof of Theorem 1.2 in the place of the polynomial P.$\Box$


Proof of Corollary 1.6 Let $m'=p_1^{\alpha_1}p_2^{\alpha_2}$, and apply Theorem 1.4 for constructing a set-system ${\cal H}$ 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. $\Box$


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