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

preprint2017arXivOpen access

Abstract

Let K={k1,k2,…,kr}K=\{k_1,k_2,\ldots,k_r\} and L={l1,l2,…,ls}L=\{l_1,l_2,\ldots,l_s\} be disjoint subsets of {0,1,…,p−1}\{0,1,\ldots,p-1\}, where pp is a prime and A={A1,A2,…,Am}A=\{A_1,A_2,\ldots,A_m\} be a family of subsets of [n][n] such that ∣Ai∣(modp)∈K|A_i|\pmod{p}\in K for all Ai∈AA_i\in A and ∣Ai∩Aj∣(modp)∈L|A_i\cap A_j|\pmod{p}\in L for i≠ji\ne j. In 1991, Alon, Babai and Suzuki conjectured that if n≥s+max⁡1≤i≤rkin\geq s+\max_{1\leq i\leq r} k_i, then ∣A∣≤(ns)+(ns−1)+⋯+(ns−r+1)|A|\leq {n\choose s}+{n\choose s-1}+\cdots+{n\choose s-r+1}. In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition n≥2s−rn\geq 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+1n\geq 2s-2r+1 or n≥s+max⁡1≤i≤rkin\geq s+\max_{1\leq i\leq r}k_i, then ∣A∣≤(n−1s)+(n−1s−1)+⋯+(n−1s−2r+1). |A|\leq{n-1\choose s}+{n-1\choose s-1}+\cdots+{n-1\choose s-2r+1}. This result strengthens the upper bound of Alon, Babai and Suzuki's conjecture when n≥2s−2n\geq 2s-2.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.