Premium
Families in posets minimizing the number of comparable pairs
Author(s) -
Balogh József,
Petříčková Šárka,
Wagner Adam Zsolt
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22604
Subject(s) - partially ordered set , mathematics , combinatorics , conjecture , property (philosophy) , lattice (music) , linear subspace , discrete mathematics , family of sets , set (abstract data type) , pure mathematics , computer science , philosophy , physics , epistemology , acoustics , programming language
Given a graded poset P we say a family F ⊆ P is centered if it is obtained by ‘taking sets as close to the middle layer as possible.’ A poset P is said to have the centeredness property if for any M , among all families of size M in P , centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice{ 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 also has the centeredness property, provided n is sufficiently large compared with k . We show that this conjecture is false for all k ≥ 2 and investigate the range of M for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of F q n has the centeredness property. Several open questions are also given.