6 research outputs found
Alon–Babai–Suzuki’s inequalities, Frankl–Wilson type theorem and multilinear polynomials
No full textAbstractLet K={k1,k2,…,kr} and L={l1,l2,…,ls} be subsets of {0,1,…,p−1} such that K∩L=0̸, where p is a prime. Let F={F1,F2,…,Fm} be a family of subsets of [n]={1,2,…,n} with |Fi| (modp) ∈K for all Fi∈F and |Fi∩Fj| (modp) ∈L for any i≠j. Every subset Fi of [n] can be represented by a binary code a=(a1,a2,…,an) such that aj=1 if j∈Fi and aj=0 if j∉Fi. Alon–Babai–Suzuki proved in non-modular version that if ki≥s−r+1 for all i, then |F|≤∑i=s−r+1s(ni). 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+maxiki 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+maxiki, then the above bound holds. But we prove the same bound under dropping the opposite condition n≥s+maxiki. 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])
Alon-Babai-Suzuki's Conjecture Related to Binary Codes in Nonmodular Version
No full text Let and be sets of nonnegative integers. Let be a family of subsets of with for each and for any . Every subset of can be represented by a binary code a such that if and if . Alon et al. made a conjecture in 1991 in modular version. We prove Alon-Babai-Sukuki's Conjecture in nonmodular version. For any and with , .</p
Alon-Babai-Suzuki's Conjecture Related to Binary Codes in Nonmodular Version
No full textLet K={k1,k2,…,kr} and L={l1,l2,…,ls} be sets of nonnegative integers. Let ℱ={F1,F2,…,Fm} be a family of subsets of [n] with [Fi]∈K for each i and |Fi∩Fj|∈L for any i≠j. Every subset Fe of [n] can be represented by a binary code a=(a1,a2,…,an) such that ai=1 if i∈Fe and ai=0 if i∉Fe. Alon et al. made a conjecture in 1991 in modular version. We prove Alon-Babai-Sukuki's Conjecture in nonmodular version. For any K and L with n≥s+max⁡ki, |F|≤(n-1s)+(n-1s-1)+⋯+(n-1s-2r+1)
