pith. sign in

arxiv: 1701.00585 · v1 · pith:2UHLZQCDnew · submitted 2017-01-03 · 🧮 math.CO

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

classification 🧮 math.CO
keywords chooseconjectureldotsalonbabaisuzukicdotspmod
0
0 comments X
read the original 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|\pmod{p}\in K$ for all $A_i\in A$ and $|A_i\cap A_j|\pmod{p}\in L$ for $i\ne j$. In 1991, Alon, Babai and Suzuki conjectured that if $n\geq s+\max_{1\leq i\leq r} k_i$, then $|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\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\geq 2s-2r+1$ or $n\geq s+\max_{1\leq i\leq r}k_i$, then \[ |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\geq 2s-2$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.