Alon-Babai-Suzuki's inequalities, Frankl-Wilson type theorem and multilinear polynomials

作者：Sohn Gyoyong; Ryoo Cheon Seoung; Kim Philsu; Hwang Kyung Won^*; Hwang Jinsoo

来源：Applied Mathematics Letters, 2011, 24(9): 1477-1480.

DOI：10.1016/j.aml.2010.12.014

• Alon-Babai-Suzuki's inequalities
• Frankl-Wilson theorem
• Multilinear polynomials

Let K = {k(1), k(2), .... k(r)} and L = {l(1), l(2,) .... l(s)} be subsets of {0, 1, .... p - 1} such that K boolean AND L = theta, where p is a prime. Let F = {F(1), F(2), .... F(m)) be a family of subsets of [n] = {1, 2, ..., n} with [Fi] (mod p) epsilon K for all F(i) epsilon F and [F(i) boolean AND F(j)] (mod p) epsilon L for any i not equal j. Every subset F(i) of [n] can be represented by a binary code a = (a(1), a(2), ..., a(n)) such that a(j) = 1 if j epsilon F(i) and aj = 0 if j is not an element of F(i). Alon-Babai-Suzuki proved in non-modular version that if k(i) >= s - r + 1 for all i, then [F] <= Sigma(s)(i=s-r+1) ((n)(i)) We generalize it in modular version. Alon-Babai-Suzuki also proved that the above bound still holds under r(s - r + 1) <= p - 1 and n >= s + max, k(i) in modular version. Alon-Babai-Suzuki made a conjecture that if they drop one condition r(s - r + 1) <= p - 1 among r(s - r + 1) <= p - 1 and n >= s + max, k(i), then the above bound holds. But we prove the same bound under dropping the opposite condition n >= s + max(i) k(i). So we prove the same bound under only condition r(s - r + 1) <= p - 1. This is a generalization of Frankl-Wilson theorem (Frankl and Wilson, 1981 [2]).

• 出版日期2011-9