A proof of Alon-Babai-Suzuki's conjecture and multilinear polynomials

作者：Hwang Kyung Won^*; Kim Younjin

来源：European Journal of Combinatorics, 2015, 43: 289-294.

DOI：10.1016/j.ejc.2014.08.027

Let K = {k(1), k(2), ... , k(r)} and L = (l(1), l(2), ... , l(s)} be disjoint subsets of {0, 1, ... p - 1), where p is a prime and F = {F-1, F-2, ... , F-m} be a family of subsets of [n] such that vertical bar F-1 vertical bar (mod p) is an element of K for all F-i is an element of F and vertical bar F-i boolean AND F-j vertical bar (mod p) is an element of L for i not equal j. In 1991 Alon, Babai and Suzuki conjectured that if n >= s + max(1 <= i <=)r k(i), then vertical bar F vertical bar <= (n/s) + (n/s-1) + ... + (n/s-r+1). In this paper we prove this conjecture.

• 出版日期2015-1