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

N. Alon, L. Babai, H. Suzuki

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)165-180
Number of pages16
JournalJournal of Combinatorial Theory, Series A
Volume58
Issue number2
DOIs
StatePublished - Nov 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems'. Together they form a unique fingerprint.

Cite this