Skip to main content
4 of 6
added 562 characters in body
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

Minimum number of elements needed to represent a lattice with a union-closed family of sets

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

Fabius Wiesner
  • 988
  • 1
  • 9
  • 23