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

2017/01/03 by Xin Wang, Wang, Xin, Hengjia Wei +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1701.00585

arxiv created 2017/01/03 · arxiv updated 2017/01/04

Abstract

Let K=\k₁,k₂,…,k_r\ and L=\l₁,l₂,…,l_s\ be disjoint subsets of \0,1,…,p-1\, where p is a prime and A=\A₁,A₂,…,A_m\ be a family of subsets of [n] such that |A_i|\pmodp∈ K for all A_i∈ A and |A_i∩ A_j|\pmodp∈ L for i≠ j. In 1991, Alon, Babai and Suzuki conjectured that if n≥ s+max_{1≤ i≤ r} k_i, then |A|≤ n\choose s+n\choose s-1+⋯+n\choose s-r+1. In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition n≥ 2s-r. In 2015, Hwang and Kim verified the conjecture of Alon, Babai and Suzuki. In this paper, we will prove that if n≥ 2s-2r+1 or n≥ s+max_{1≤ i≤ r}k_i, then |A|≤n-1\choose s+n-1\choose s-1+⋯+n-1\choose s-2r+1. This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when n≥ 2s-2.

Related

• New upper bounds for the size of set systems with restricted intersections modulo prime powers
• On non-empty cross-intersecting families
• A Common Generalization to Theorems on Set Systems with L-intersections
• Partitioning all k-subsets into r-wise intersecting families
• A New Quadratic Bound for the Manickam-Miklós-Singhi Conjecture