Families in posets minimizing the number of comparable pairs

DOI10.1002/JGT.22604MaRDI QIDQ6134650zbMATH OpenOpenAlexFDO

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

Publication date 22 August 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05427

zbMATH Keywords

posetBoolean latticeSperner's theoremKleitman's theoremcomparable pair

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Given a poset $P$ we say a family $mathcalFsubseteqP$ 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,ldots,k}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $kgeq2$ 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 $mathbb{F}_q^n$ has the centeredness property. Several open questions are also given.

Recommendations

• Every poset has a central element
• Families of subsets without a given poset in double chains and Boolean lattices
• Progress on poset-free families of subsets
• Packing posets in the Boolean lattice.
• Comparable pairs in families of sets

Cites work

• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 3256524 (Why is no real title available?)
• A Unimodality Result in the Enumeration of Subgroups of a Finite Abelian Group
• Comparable pairs in families of sets
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Sperner's theorem and a problem of Erdős, Katona and Kleitman
• Subsets of posets minimising the number of chains
• Supersaturation in posets and applications involving the container method
• Supersaturation in the Boolean lattice

Cited in

(3)

• Supersaturation in posets and applications involving the container method
• Minimum saturated families of sets
• An optimal ancestry scheme and small universal posets

This page was built for publication: Families in posets minimizing the number of comparable pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134650)