0
$\begingroup$

I know that it is possible to represent every finite lattice $L$ with a union-closed family $\mathcal{F}$ containing the empty set: for every $x\in L$, let $S_x=\{y\in L\, :\, y\not\geq x\}$ and $\mathcal{F} = \{S_x :\, x\in L\}$ (see this question).

However, the number of elements in the universe $|U(\mathcal{F})| =|L|$ is not necessarily minimal: we can remove some of them and still have a family representing the lattice.

Here are a few examples where the removed (not needed) elements are depicted in red:

The powerset:

enter image description here

or: enter image description here

the above slightly modified: enter image description here

this example family:

enter image description here

I have done the above with a program that tries to remove one element at a time. It seems that the result does not depend on the order of tries.

Is it possible to identify systematically the elements that are not removed and/or determine or estimate the minimum number of elements needed for a given lattice based on some structure of it?

Maybe the only needed elements are those with out-degree exactly $1$?

EDIT: the following further examples seem to support the above hypothesis:

this union-closed family:

enter image description here

the Tamari lattice of order 4:

enter image description here

the Stanley lattice N=4

enter image description here

Following the hint in the comment, let $\mathcal{F} = \{S_x :\, x\in L\}$ and $S_x=\{y\in L\, :\, y\not\geq x,\, y \not= a \land b\}$, i.e. $y$ must be meet-irreducible.

Then $S_t \cup S_u = \{y\in L\, :\, y\not\geq t \lor y\not\geq u,\, y \not= a \land b\} = \{y\in L\, :\, y\not\geq t \lor u,\, y \not= a \land b\} = S_{t \lor u}$, because $y \ge t \lor u \iff y \ge t$ and $y \ge u$.

Now suppose $S_t = S_u$ for some $t \not= u$. Then any $y$ such that $y \ge t$ and $y \not\ge u$ must be meet-reducible, i.e. $y = a \land b$. But then $a \ge t$, $b \ge t$, $a \not\ge u$ or $b \not\ge u$. Then $a \ge t$ and $a \not\ge u$, or $b \ge t$ and $b \not\ge u$. Then $a$ or $b$ must be meet-reducible. But we cannot continue indefinitely, therefore $S_t = S_u \iff t = u$.

Let $t$ be meet-irreducible and $u$ the least element $x \gt y$, then $t \in S_u$ and $t \not\in S_t$. If $y \ge u$ then $y \ge t$. If we remove $t$ from the universe, since $t$ is meet-irreducible, then any $y \ge t$, $y \not= t$, must satisfy $y \ge u$. Therefore $S_t = S_u$ and we cannot remove any of the meet-irreducible elements.

Although $\mathcal{F}$ is a valid representation of the lattice, I think that it is not proved that the number of elements of its universe is minimal, should we find a different construction. Is it possible to prove or disprove it?

$\endgroup$
8
  • 1
    $\begingroup$ "Maybe the only needed elements are those with out-degree exactly 1?": in lattice theory these are called the meet-irreducible elements, and I think that yes this should be easy to show. $\endgroup$ Commented Jul 11 at 21:09
  • 1
    $\begingroup$ See for example my answer at the other question: mathoverflow.net/a/469052/25028 $\endgroup$ Commented Jul 11 at 21:15
  • $\begingroup$ @SamHopkins thank you for your comments. I think that I managed to do the easy part, and can be satisfied by having shown that we can restrict the elements to only meet-irreducible ones. However, proving or disproving that this is a representation with a minimum number of elements seems more difficult. $\endgroup$ Commented Jul 14 at 8:44
  • 1
    $\begingroup$ @FabiusWiesner: we can't express a meet-irreducible element as a meet of other elements, so it must appear in any set of elements that generate $L$ using the meet operation. $\endgroup$ Commented Jul 14 at 13:59
  • $\begingroup$ @RichardStanley excuse me, but with a union closed family aren't we generating $L$ with the join operation rather than the meet operation? $\endgroup$ Commented Jul 14 at 14:30

1 Answer 1

0
$\begingroup$

Let $\mathcal{F} = \{S_x :\, x\in L\}$ and $S_x=\{y\in L\, :\, y\not\geq x,\, y \not= a \land b\}$, i.e. $y$ must be meet-irreducible, for the following lattice $L$:

enter image description here

where the meet-irreducible elements are the white ones: $1$, $2$, $3$, $4$.

Then $\mathcal{F} = \{\emptyset,\{2,4\},\{1,4\},\{1,2,4\},\{1,2,3\},\{1,2,3,4\}\}$, but the representation is not minimal because we can remove $4$ from all sets and $1$ from $\{1,2,3\}$ to get $\mathcal{F} = \{\emptyset,\{2\},\{1\},\{1,2\},\{2,3\},\{1,2,3\}\}$.

That said, for what I know, I think that the best that we can say is this answer to a related question that was pointed out in the comments.

$\endgroup$

You must log in to answer this question.

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