TY - JOUR

T1 - Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems

AU - Alon, N.

AU - Babai, L.

AU - Suzuki, H.

N1 - Funding Information:
We give a very simple new proof of the celebrated intersection theorem of D. K. Ray-Chaudhuri and R. M. Wilson. The new proof yields a generalization to nonuniform set systems. Let Generalized Ray-Chaudhuri-Wilson Theorem. Let K= {k,, . . . . k,}, L = {It, . . . . I,), and assume ki > s - r for all i. Let 9 be a family of subsets of an n-element set. Suppose that 14 E K for each FE%-; and lEnF/ EL for each pair of distinct sets I?, FES. Then IFI< N(n, s, r). The proof easily generalizes to equicardinal * Research supported in part by a Bat Sheva de Rothschild grant and by the Fund Research administered by the Israel Academy of Sciences. + Research supported in part by NSF Grant CCR-8710078 and Hungarian Foundation for Scientific Research Grant 1812.

PY - 1991/11

Y1 - 1991/11

N2 - We give a very simple new proof of the celebrated intersection theorem of D. K. Ray-Chaudhuri and R. M. Wilson. The new proof yields a generalization to nonuniform set systems. Let N(n,s,r) = ( n s) + ( n s-1) + ⋯( n s-r+1).Generalized Ray-Chaudhuri-Wilson Theorem. Let K = {k1,...,kr}, L = {l1,...,ls}, and assume ki > s - r for all i. Let F be a family of subsets of an n-element set. Suppose that |F| ε{lunate} K for each F ε{lunate} F; and |E ∩ F| ε{lunate} L for each pair of distinct sets E, F ε{lunate} F. Then |F| ≤ N(n, s, r). The proof easily generalizes to equicardinal.

AB - We give a very simple new proof of the celebrated intersection theorem of D. K. Ray-Chaudhuri and R. M. Wilson. The new proof yields a generalization to nonuniform set systems. Let N(n,s,r) = ( n s) + ( n s-1) + ⋯( n s-r+1).Generalized Ray-Chaudhuri-Wilson Theorem. Let K = {k1,...,kr}, L = {l1,...,ls}, and assume ki > s - r for all i. Let F be a family of subsets of an n-element set. Suppose that |F| ε{lunate} K for each F ε{lunate} F; and |E ∩ F| ε{lunate} L for each pair of distinct sets E, F ε{lunate} F. Then |F| ≤ N(n, s, r). The proof easily generalizes to equicardinal.

UR - http://www.scopus.com/inward/record.url?scp=44949282626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44949282626&partnerID=8YFLogxK

U2 - 10.1016/0097-3165(91)90058-O

DO - 10.1016/0097-3165(91)90058-O

M3 - Article

AN - SCOPUS:44949282626

SN - 0097-3165

VL - 58

SP - 165

EP - 180

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

IS - 2

ER -