Set-systems with restricted multiple intersections (Q5958836)

Summary: We give a generalization for the Deza-Frankl-Singhi theorem in case of multiple intersections. More exactly, we prove, that if \({\mathcal H}\) is a set-system, which satisfies that for some \(k\), the \(k\)-wise intersections occupy only \(\ell\) residue-classes modulo a \(p\) prime, while the sizes of the members of \({\mathcal H}\) are not in these residue-classes, then the size of \({\mathcal H}\) is at most \[ (k-1)\sum_{i=0}^{\ell}{n\choose i}. \] This result considerably strengthens an upper bound of \textit{Z. Füredi} [Discrete Math. 47, No. 1, 129-132 (1983; Zbl 0531.05002)], and gives partial answer to a question of \textit{V. T. Sós} [Colloq. Int. Theorie Comb., Roma 1973, Tomo II, 223-233 (1976; Zbl 0361.05022)]. As an application, we give a direct, explicit construction for coloring the \(k\)-subsets of an \(n\) element set with \(t\) colors, such that no monochromatic complete hypergraph on \(\exp{(c(\log m)^{1/t}(\log \log m)^{1/(t-1)})}\) vertices exists.