next up previous
Next: Bibliography Up: Superpolynomial Size Set-Systems with Previous: An Application: Ramsey Graphs

Open Problems

Problem 1 (Barrington, Beigel and Rudich [2]) Does there exist a polynomial P in n variables, with integer coefficients, of degree $d=o(\sqrt n)$, which weakly represents the n-variable OR function modulo 6? (Recall, that this means that $P(0,0,\ldots,0)=0$, and $P(x)\not\equiv 0\bmod{6}$ for any $x\in\{0,1\}^n, x\ne 0$.) If the answer is yes for some $d=n^\varepsilon$ and the polynomials are explicitly constructed, then our method yields explicit Ramsey-graphs on

\begin{displaymath}\exp\bigg(c{(\log h)^{1/\varepsilon}\over (\log
\log h)^{{1/\varepsilon}-1}}\bigg)\end{displaymath}

vertices, with no complete subgraph and no independent set of size h. For symmetric polynomials, Barrington, Beigel and Rudich [2] have shown that the degree is $\Omega(\sqrt{n})$. Showing only the existence of polynomials, weakly representing the OR function with degree $o(\sqrt n)$, would also have considerable theoretical interest, since this result would imply the existence of larger set-systems in Theorem 1.2. Here we should also mention that the best lower bound is due to G. Tardos and Barrington [9]. They proved that if the modulus m has r>1 different prime divisors, then every polynomial, weakly representing the function ORn modulo m, has degree at least

\begin{displaymath}(\log n)^{1/(r-1)}.\end{displaymath}


Problem 2 Does there exist a quadratic polynomial P in n variables, with integer coefficients, which weakly represents the n-variable OR function modulo $2^\alpha3^\beta$, where both $2^\alpha$ and $3^\beta$ are $o(\sqrt n)$? If the answer is yes, then combining this P and the polynomial of Barrington, Beigel and Rudich [2], we would obtain a polynomial, satisfying the requirements of Problem 1.


Problem 3 It remains an open question whether, for a fixed positive integer m, a better than exponential ($\exp(o(n))$ upper bound holds for the size of set-systems satisfying that the size of each set is divisible by m while the sizes of their pairwise intersections are not divisible by m. This problem is open even for m=6. Our main result shows that if m is not a prime power then no polynomial upper bound (O(nc)) holds. (If m is a prime power then a polynomial upper bound holds by Frankl - Wilson 1.1.) Problem 4 If in Problem 3 we assume additionally that the sizes of the pairwise intersections occupy only two residue classes mod m then there may even be a polynomial upper bound (perhaps O(n2)), yet we are not aware of any better-than-exponential upper bound even for this case. This, too, is open for m=6.


Acknowledgments. The author wishes to thank Zoltán Király and David Mix Barrington for fruitful discussions and to Péter Frankl for valuable comments and suggestions. The author is especially grateful to Laci Babai for numerous helpful remarks and suggestions. The author acknowledges the support of grants OTKA T030059, FKFP 0607/1999, AKP 97-56 2,1.


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