An extremal problem for sets with applications to graph theory

Research output: Contribution to journalArticle

32 Scopus citations

Abstract

Let X1, ..., Xn be n disjoint sets. For 1 ≤ i ≤ n and 1 ≤ j ≤ h let Aij and Bij be subsets of Xi that satisfy |Aij| ≤ ri and |Bij| ≤ si for 1 ≤ i ≤ n, 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bij) = {circled division slash} for 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bil) ≠ {circled division slash} for 1 ≤ j < l ≤ h. We prove that h≤ Π i=1 n ri+si ri. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).

Original languageEnglish (US)
Pages (from-to)82-89
Number of pages8
JournalJournal of Combinatorial Theory, Series A
Volume40
Issue number1
DOIs
StatePublished - Sep 1985

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'An extremal problem for sets with applications to graph theory'. Together they form a unique fingerprint.

Cite this