On mod-\(p\) Alon-Babai-Suzuki inequality (Q5926295)
From MaRDI portal
scientific article; zbMATH DE number 1570901
Language | Label | Description | Also known as |
---|---|---|---|
English | On mod-\(p\) Alon-Babai-Suzuki inequality |
scientific article; zbMATH DE number 1570901 |
Statements
On mod-\(p\) Alon-Babai-Suzuki inequality (English)
0 references
21 August 2003
0 references
The authors prove the following theorem: Let \(p\) be a prime number and \(r, s\) be two positive integers with \(2s-r\leq n\). Moreover, let \(K\) and \(L\) be disjoint subsets of \(\{0, 1,\dots ,p-1\}\) with \(|K|=r\) and \(|L|=s\). If \(\mathcal{F}\) is a family of subsets of an \(n\)-element set such that \(|F|\in K \pmod p\) for each \(F\in\mathcal{F}\), and \(|E \cap F|\in L\) \((\text{mod} p)\) for each pair of distinct sets \(E, F\in\mathcal{F}\), then \[ |\mathcal{F}|\leq \binom {n}{s}+\binom {n}{s-1}+\cdots +\binom{n}{s-r+1}. \] Thus a conjecture of \textit{N. Alon, L. Babai} and \textit{H. Suzuku} [J. Comb. Theory, Ser. A 58, 165-180 (1991; Zbl 0751.05009)] is confirmed to a large extent.
0 references
intersecting family
0 references
extremal set problem
0 references
Frankl-Ray-Chaudhuri-Wilson inequality
0 references
incidence matrix
0 references
family of subsets
0 references