1
$\begingroup$

Let $L$ be a finite lattice. Then $L$ is generated by its join-irreducible elements $J(L)$ or alternatively its meet-irreducible elements $M(L)$.

If $S \subseteq L$ is a sub join-semilattice then $|M(S)| \leq |M(L)|$. This follows by the self-duality of finite join-semilattices with join-preserving maps i.e. dually we have a surjective quotient $L^{op} \twoheadrightarrow S^{op}$ which implies $|J(S^{op})| \leq |J(L^{op})|$ because the join-irreducibles form the least set of generators.

However one can have $|J(S)| > |J(L)|$ e.g. take $L = \mathbf{2}^3$ and remove an atom to form $S$.

My question is whether there exist non-trivial bounds on $\max_{S \subseteq L}(|J(S)| - |J(L)|)$ i.e. one fixes $L$ and varies over the sub join-semilattices $S$. I am mainly interested in the case $L = \mathbf{2}^n$.

In summary, how many more join-irreducibles can there be in a sub join-semilattice of a finite lattice?

Thanks for any help.

Improve this question
$\endgroup$
4
  • $\begingroup$ This has a smell of Frankl's union closed sets conjecture about it. Gerhard "Ask Me About System Design" Paseman, 2012.09.20 $\endgroup$
    – Gerhard Paseman
    Sep 20, 2012 at 23:43
  • $\begingroup$ For $2^n$ one can remove all elements of ranks $1\leq k<n/2$, giving ${n \choose \lfloor n/2\rfloor}$ join-irreducibles. Perhaps this is the maximum possible for a join-semilattice of a finite lattice with $n$ join-irreducibles. $\endgroup$
    – Richard Stanley
    Sep 22, 2012 at 1:22
  • $\begingroup$ @Richard Stanley: Thanks, your comment shows there may be exponentially many more. However in the example I gave |J(S)| = 4, whereas removing all the atoms of $2^3$ only gives 3. Do you have any reason for thinking your bound is maximal or nearly maximal? $\endgroup$
    – Rob Myers
    Sep 22, 2012 at 18:00
  • $\begingroup$ In fact, my bound can be improved. Exercise 4.29 in EC1 (math.mit.edu/~rstan/ec/ec1.pdf) is related. The solution mentions a bound of Kleitman. Kleitman (private communication) constructs an order ideal of $2^n$ with at least ${n\choose \lfloor n/2\rfloor}(1+\frac 1n)$ meet-irreducibles. Dualizing gives a join-semilattice of $2^n$ with this many join-irreducibles. Conceivably the answer to Exercise 4.29 and is also equal to the greatest number of join-irreducibles of any join-semilattice of $2^n$, or perhaps of any join-semilattice of a finite lattice with $n$ join-irreducibles. $\endgroup$
    – Richard Stanley
    Sep 23, 2012 at 17:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.