A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo p

DOI10.1016/J.DISC.2017.08.019MaRDI QIDQ2411601zbMATH OpenOpenAlexWikidataFDO

Authors Xin Wang, Hengjia Wei, Gennian Ge

Publication date 24 October 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.00585

zbMATH Keywords

Alon-Babai-Suzuki conjectureextremal set theoryFrankl-Ray-Chaudhuri-Wilson theoremsrestricted intersections

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Extremal set theory (05D05)

Abstract: Let $K=k_1,k_2,ldots,k_r$ and $L=l_1,l_2,ldots,l_s$ be disjoint subsets of $0,1,ldots,p-1$, where $p$ is a prime and $A=A_1,A_2,ldots,A_m$ be a family of subsets of $[n]$ such that $|A_i|pmodpinK$ for all $A_{i}inA$ and $|A_{i}cap{A}_j|pmodpinL$ for $iej$. In 1991, Alon, Babai and Suzuki conjectured that if $ngeqs+ma{x}_{1leqileqr}{k}_i$, then $|A|leqnchooses+nchooses-1+cdots+nchooses-r+1$. In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition $ngeq2s-r$. In 2015, Hwang and Kim verified the conjecture of Alon, Babai and Suzuki. In this paper, we will prove that if $ngeq2s-2r+1$ or $ngeqs+ma{x}_{1leqileqr}{k}_i$, then [ |A|leq{n-1choose s}+{n-1choose s-1}+cdots+{n-1choose s-2r+1}. ] This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when $ngeq2s-2$.

Recommendations

• A new Alon-Babai-Suzuki-type inequality on set systems
• On set systems with restricted k-wise L-intersection modulo a prime, and beyond
• scientific article; zbMATH DE number 1088263
• Set systems with restricted \(k\)-wise \(\mathcal{L}\)-intersections modulo a prime number
• On mod-p Alon-Babai-Suzuki inequality
• Set systems with restricted \(t\)-wise intersections modulo prime powers
• Extremal set systems with weakly restricted intersections
• Set systems with restricted intersections modulo prime powers
• A proof of Furstenberg's conjecture on the intersections of \(\times p\)- and \(\times q\)-invariant sets
• Constructive upper bounds for intersecting set systems

Cites work

• A Note on Fisher's Inequality for Balanced Incomplete Block Designs
• A proof of Alon-Babai-Suzuki's conjecture and multilinear polynomials
• scientific article; zbMATH DE number 3049937 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems with geometric consequences
• Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems
• On \(k\)-wise set-intersections and \(k\)-wise Hamming-distances
• On generalizations of the deBruijn-Erdős theorem
• On mod-p Alon-Babai-Suzuki inequality
• On t-designs
• Set systems with \(\mathcal L\)-intersections modulo a prime number
• Set systems with restricted \(k\)-wise \(\mathcal{L}\)-intersections modulo a prime number

Cited in

(9)

• On set systems with restricted intersections modulo p and p-ary t-designs
• Standard monomials for q-uniform families and a conjecture of Babai and Frankl
• A new Alon-Babai-Suzuki-type inequality on set systems
• A proof of Alon-Babai-Suzuki's conjecture and multilinear polynomials
• Alon-Babai-Suzuki's inequalities, Frankl-Wilson type theorem and multilinear polynomials
• On mod-p Alon-Babai-Suzuki inequality
• Set systems with restricted intersections modulo prime powers
• Set systems with restricted symmetric sets of Hamming distances modulo a prime number
• Alon-Babai-Suzuki's conjecture related to binary codes in nonmodular version

This page was built for publication: A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo \(p\)

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