Families in posets minimizing the number of comparable pairs

DOI10.1002/JGT.22604zbMATH Open1525.05183arXiv1703.05427OpenAlexW3037411436MaRDI QIDQ6134650FDOQ6134650

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

Publication date: 22 August 2023

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

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.

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)

Cites Work

• Title not available (Why is that?)
• A Unimodality Result in the Enumeration of Subgroups of a Finite Abelian Group
• Sperner's Theorem and a Problem of Erdős, Katona and Kleitman
• Title not available (Why is that?)
• Comparable pairs in families of sets
• Supersaturation in the Boolean lattice
• Subsets of posets minimising the number of chains
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Supersaturation in posets and applications involving the container method

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)