A proof of Alon–Babai–Suzuki's conjecture and multilinear polynomials. (January 2015)

• Record Type: Journal Article
• Authors: Hwang, Kyung-Won; Kim, Younjin
• Is Part Of: European journal of combinatorics. Volume 43(2015:Jan.)
• Page Start: 289
• Page End: 294
• Publication Date: 2015-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2014.08.027
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 | F i | (mod p ) ∈ K for all F i ∈ F and | F i ∩ F j | (mod p ) ∈ L for i ≠ j . In 1991 Alon, Babai and Suzuki conjectured that if n ≥ s + max 1 ≤ i ≤ r k i, then | F | ≤ n s + n s − 1 + ⋯ + n s − r + 1 . In this paper we prove this conjecture.