Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
This has a smell of Frankl's union closed sets conjecture about it. Gerhard "Ask Me About System Design" Paseman, 2012.09.20 –  Gerhard Paseman Sep 20 '12 at 23:43
    
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. –  Richard Stanley Sep 22 '12 at 1:22
    
@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? –  Rob Myers Sep 22 '12 at 18:00
    
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. –  Richard Stanley Sep 23 '12 at 17:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.