Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-06T00:33:17.204Z Has data issue: false hasContentIssue false

Constructing Large Set Systems with Given Intersection Sizes Modulo Composite Numbers

Published online by Cambridge University Press:  09 October 2002

SAMUEL KUTIN
Affiliation:
Center for Communications Research, 805 Bunn Drive, Princeton, NJ 08540, USA (e-mail: kutin@idaccr.org)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider k-uniform set systems over a universe of size n such that the size of each pairwise intersection of sets lies in one of s residue classes mod q, but k does not lie in any of these s classes. A celebrated theorem of Frankl and Wilson [8] states that any such set system has size at most (ns) when q is prime. In a remarkable recent paper, Grolmusz [9] constructed set systems of superpolynomial size Ω(exp(c log2n/log log n)) when q = 6. We give a new, simpler construction achieving a slightly improved bound. Our construction combines a technique of Frankl [6] of ‘applying polynomials to set systems’ with Grolmusz's idea of employing polynomials introduced by Barrington, Beigel and Rudich [5]. We also extend Frankl's original argument to arbitrary prime-power moduli: for any ε > 0, we construct systems of size ns+g(s), where g(s) = Ω(s1−ε). Our work overlaps with a very recent technical report by Grolmusz [10].

Information

Type
Research Article
Copyright
2002 Cambridge University Press