On set systems with restricted intersections modulo a composite number. (Extended abstract)

DOI10.1007/BFB0045075MaRDI QIDQ4364578zbMATH OpenFDO

Authors Vince Grolmusz

Publication date 1 June 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0045075

zbMATH Keywords

Frankl-Wilson theoremintersecting familymultivariate polynomialsrepresentation of Boolean function

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorics in computer science (68R05)

Review text

The following theorem is proved: Let \(m\) be a positive non-prime-power integer, and suppose that \(m\) has \(r>1\) different prime divisors. Then, for every integer \(n>0\), there exists an explicitly constructible family \(F\) of subsets of \(\{1,\dots, n\}\) of size \(\exp(c(\log n)^r/(\log\log n)^{r- 1})\) with some \(c>0\) such that \(|X|\equiv 0\pmod m\) and \(|X\cap Y|\not\equiv 0\pmod m\) for all \(X,Y\in F\). The proof uses a low-degree polynomial construction of \textit{D. A. M. Barrington}, \textit{R. Beigel} and \textit{S. Rudich} [Comput. Complexity 4, No. 4, 367-382 (1994; Zbl 0829.68057)] and a new method for constructing set systems from multivariate polynomials. The result also settles a related conjecture of Babai and Frankl in the negative. For the entire collection see [Zbl 0869.00027].

Recommendations

• Constructing Large Set Systems with Given Intersection Sizes Modulo Composite Numbers
• Set systems with restricted \(t\)-wise intersections modulo prime powers
• Set systems with restricted intersections modulo prime powers
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs

Cited in

(9)

• Set systems with restricted \(t\)-wise intersections modulo prime powers
• Set systems with no union of cardinality 0 modulo \(m\)
• Extremal set systems with restricted \(k\)-wise intersections.
• Secure computation with preprocessing via function secret sharing
• A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo \(p\)
• Constructing Ramsey graphs from Boolean function representations
• scientific article; zbMATH DE number 1919511 (Why is no real title available?)
• Constructing set systems with prescribed intersection sizes
• Set systems with restricted intersections modulo prime powers

This page was built for publication: On set systems with restricted intersections modulo a composite number. (Extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4364578)