Skip to main navigation Skip to search Skip to main content

Intersecting P-free families

Research output: Contribution to journalArticlepeer-review

Abstract

We study the problem of determining the size of the largest intersecting P-free family for a given partially ordered set (poset) P. In particular, we find the exact size of the largest intersecting B-free family where B is the butterfly poset and classify the cases of equality. The proof uses a new generalization of the partition method of Griggs, Li and Lu. We also prove generalizations of two well-known inequalities of Bollobás and Greene, Katona and Kleitman in this case. Furthermore, we obtain a general bound on the size of the largest intersecting P-free family, which is sharp for an infinite class of posets originally considered by Burcsi and Nagy, when n is odd. Finally, we give a new proof of the bound on the maximum size of an intersecting k-Sperner family and determine the cases of equality.

Original languageEnglish (US)
Pages (from-to)61-83
Number of pages23
JournalJournal of Combinatorial Theory. Series A
Volume151
DOIs
StatePublished - Oct 1 2017
Externally publishedYes

Keywords

  • Antichain
  • Butterfly
  • Forbidden poset
  • Intersecting set family
  • Sperner

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Intersecting P-free families'. Together they form a unique fingerprint.

Cite this