Families in posets minimizing the number of comparable pairs

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

Research output: Contribution to journalArticlepeer-review

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)
Pages (from-to)655-676
Number of pages22
JournalJournal of Graph Theory
Volume95
Issue number4
DOIs
StatePublished - Dec 1 2020

Keywords

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

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