Skip to main content
added 41 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

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?

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. Is it possible to prove or disprove it?

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?

added 1311 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

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. Is it possible to prove or disprove it?

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

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. Is it possible to prove or disprove it?

added 562 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23

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

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$?

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

added 73 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23
Loading
added 30 characters in body
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23
Loading
Source Link
Fabius Wiesner
  • 988
  • 1
  • 9
  • 23
Loading