Set-systems with restricted multiple intersections
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.
- On two set-systems with restricted cross-intersections
- Set systems with union and intersection constraints
- Extremal set systems with weakly restricted intersections
- Set systems with restricted intersections modulo prime powers
- Intersection Properties of Systems of Finite Sets
- scientific article; zbMATH DE number 3596845
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
- Extremal set systems with restricted \(k\)-wise intersections.
- Union-intersecting set systems
- Publication:5750908
- Set systems with three intersections
- Set systems with no union of cardinality 0 modulo \(m\)
- Extremal set systems with restricted \(k\)-wise intersections.
- Multiply intersecting families of sets
- Ryser's conjecture for \(t\)-intersecting hypergraphs
- Improved bounds on families under \(k\)-wise set-intersection constraints
- Co-orthogonal codes
- Set constraints with intersection
- scientific article; zbMATH DE number 4185671 (Why is no real title available?)
This page was built for publication: Set-systems with restricted multiple intersections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958836)
