Families in posets minimizing the number of comparable pairs

preprint2020arXivOpen access

Abstract

Given a poset PP we say a family F⊆P\mathcal{F}\subseteq P is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset PP is said to have the centeredness property if for any MM, among all families of size MM in PP, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice {0,1}n\{0,1\}^n has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset {0,1,…,k}n\{0,1,\ldots,k\}^n also has the centeredness property, provided nn is sufficiently large compared to kk. We show that this conjecture is false for all k≥2k\geq 2 and investigate the range of MM for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of Fqn\mathbb{F}_q^n has the centeredness property. Several open questions are also given.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.