2
$\begingroup$

Let $(P,\leq)$ be a finite poset that contains a (global) minimal element $0$ and a (global) maximal element $1$. We say that a subset $U \subset P$ is upward closed if $x \in U$ and $y \geq x$ forces $y \in U$. Given an arbitrary subset $A \subset P$, let $A^+$ be the smallest upward closed subset of $P$ containing $A$. We say that $P$ satisfies Property (X) if the following holds:

Let $U \subset P$ be any nonempty upward closed subset whose complement $D := P - U$ is also nonempty. For every subset $A \subset D$, we have the inequality $$ \frac{|A|}{|D|} \leq \frac{|A^+ \cap U|}{|U|}, $$ where $|\bullet|$ denotes cardinality.

Has anybody encountered this, or an equivalent property before? I don't know what to search for or where to look. There is a more specific question here:

let $L$ be the poset $\{1,2,\ldots,\ell\}$ with the usual ordering, and for any integer $k > 0$ consider $P = L^k$ with the product partial order. Property X holds trivially for $k = 1$ and I have a clunky proof for $k = 2$. Does Property (X) hold for higher $k$? And if so, is there a slick proof?

$\endgroup$

1 Answer 1

4
$\begingroup$

We have $A\subset A^+\cap D$ and $(A^+\cap D)^+=A^+$, so we can assume $A=A^+\cap D$, let $V=A^+$ the problem turn into $\frac{|V|-|V\cap U|}{|P|-|U|}=\frac{|V\cap(P-U)|}{|P|-|U|}\leq\frac{|V\cap U|}{|U|}\Leftrightarrow\frac{|V|}{|P|}\leq\frac{|V\cap U|}{|U|}\Leftrightarrow|V||U|\leq|P||V\cap U|$

for all upward closed subset $U,V\subset P$.

Let $U\lor V=\{u\lor v,u\in U,v\in V\},U\land V=\{u\land v,u\in U,v\in V\}$, if $U,V$ be a upward closed subset then $U\lor V=U\cap V$. If $P$ is finite distributive lacttice, like $L^k$, then by Ahlswede-Daykin inequality, with four functions are identically $1$, we have: $|V||U|\leq|V\land U||V\lor U|\leq|P||V\cap U|$ as we want.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you, this is fantastic. I would never have found the A-D inequality on my own, your answer is another reason to love this site. $\endgroup$ Commented Mar 10, 2023 at 13:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .