Set systems with restricted intersections modulo prime powers (Q5940302): Difference between revisions

Let \(L\in\{0,1,\dots ,q-1\}\); the authors define \(r\in L\pmod q\) to mean that \(r\) is congruent modulo \(q\) to a member of \(L\); the negation is \(r\notin L\pmod q\). A set system \(\mathcal F\) is \(L\)-avoiding modulo \(q\) if \(|E|\notin L\pmod q\) for all \(E\in{\mathcal F}\), and \(L\)-intersecting modulo \(q\) if \(|E\cap F|\in L\pmod q\) for all distinct \(E,F\in{\mathcal F}\). Considering \(s\)-element sets \(L\subseteq\{0,1,\dots ,q-1\}\), they define \(m(n,s,q)\) to be the maximum cardinality \(|{\mathcal F}|\) of set systems \({\mathcal F}\) over a universe of \(n\) elements, where \({\mathcal F}\) is both \(L\)-avoiding and \(L\)-intersecting modulo \(q\). Generalizing results in [\textit{P. Frankl} and \textit{R. M. Wilson}, Intersection theorems with geometric consequences. Combinatorica 1, 357-368 (1981; Zbl 0498.05048)] it was shown in [\textit{M. Deza, P. Frankl} and \textit{N. M. Singhi}, On functions of strength \(t\). Combinatorica 3, 331-339 (1983; Zbl 0528.05012)] and [\textit{N. Alon, L. Babai} and \textit{H. Suzuki}, Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory, Ser. A 58, No. 2, 165-180 (1991; Zbl 0751.05009)] that, for prime \(p\), \(m(n,s,p)\leq \sum_{i=0}^{s}{n\choose{i}}\), a polynomial bound in \(n\). For non-prime-power modulus \(q\) with largest prime divisor \(p\), it was shown in [\textit{V. Grolmusz}, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica 20, No. 1, 71-86 (2000; Zbl 0949.05083)] that \(m(n,q-1,q)\geq\exp (\frac 1{2^rp^rr^{r-1}} \cdot\frac{(\log n)^r}{(\log\log n)^{r-1} })\). Addressing the case of prime-power moduli \(q=p^k\), the authors prove, in Theorem 1.1, that \(m(n,s,p^k)\leq\sum_{i=0}^{2^{s-1}}{n\choose{i}}\).