Maximum size of r-cross t-intersecting families

Pranshu Gupta, Yannick Mogge, Simon Piga, Bjarne Schülke

Research output: Contribution to journalArticle

42 Downloads (Pure)

Abstract

Given r families of subsets of a fixed n-set, we say that they are r-cross t-intersecting if for every choice of representatives, exactly one from each family, the common intersection of these representatives is of size at least t. We obtain a generalisation of a result by Hilton and Milner on cross intersecting families. In particular, we determine the maximum possible sum of the sizes of non-empty r-cross t-intersecting families in the case when all families are k-uniform and in the case when they are arbitrary subfamilies of the power set. Only some special cases of these results had been proved before. The method we use also yields more general results concerning measures of families instead of their sizes.
Original languageEnglish
Pages (from-to)453-458
JournalProcedia Computer Science
Volume195
DOIs
Publication statusPublished - 5 Jan 2022

Keywords

  • Erdős-Ko-Rado
  • Extremal set theory
  • Hilton-Milner
  • intersecting families

Cite this