Families in posets minimizing the number of comparable pairs

József Balogh, Šárka Petříčková, Adam Zsolt Wagner

Research output: Contribution to journalArticle

Abstract

Given a graded poset (Formula presented.) we say a family (Formula presented.) is centered if it is obtained by ‘taking sets as close to the middle layer as possible.’ A poset (Formula presented.) is said to have the centeredness property if for any (Formula presented.), among all families of size (Formula presented.) in (Formula presented.), centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice (Formula presented.) has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset (Formula presented.) also has the centeredness property, provided (Formula presented.) is sufficiently large compared with (Formula presented.). We show that this conjecture is false for all (Formula presented.) and investigate the range of (Formula presented.) for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of (Formula presented.) has the centeredness property. Several open questions are also given.

Original languageEnglish (US)
JournalJournal of Graph Theory
DOIs
StateAccepted/In press - 2020

Keywords

  • Boolean lattice
  • comparable pair
  • Kleitman's theorem
  • poset
  • Sperner's theorem

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Families in posets minimizing the number of comparable pairs'. Together they form a unique fingerprint.

  • Cite this