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

How many n-element semilattices there are?

For example, for n-element partially ordered set we can figured out, that there are $2^{n*(n-1)}$ possible sets.

And can I find all possible n-element semilattices? Or maybe there are some useful rule to generate all that kind of sets? I'm trying do something, but have nothing at all with memory problems

share|improve this question
    
oeis.org/… –  Martin Rubey Feb 16 '11 at 8:59
    
Note that the oeis sequence above counts semilatices with $n$ generators, not with $n$ elements. Also, the number of $n$-element posets is much less than $2^{n(n-1)}$ (that would be the number of reflexive relations), see oeis.org/A001035 . –  Emil Jeřábek Feb 16 '11 at 11:48

2 Answers 2

up vote 3 down vote accepted

By adding a top element to a (meet) semilattice we get a lattice. Hence the number of $n$-element semilattices is the number of $(n+1)$-element lattices. This number is treated in A006966 of Sloane.

share|improve this answer

Well, this is a partial solution... You can create semi-lattices as follows: Say $v^1,v^2,\ldots, v^k\in \mathbb{K}^l$ are arbitrary vectors . Here, $\mathbb{K}^l$ denotes the positive part of $\mathbb{R}^l,$ that is, all coordinates of these vectors are positive. You can put a coordinate-wise ordering on $\mathbb{K}^l.$ Then compute the smallest lower semi-lattice generated by these vectors by taking their infimums, for instance, $(v^1 \wedge v^2)_j=v_j^1\wedge v_j^2$ for each coordinate j. According to theory, this lower semi-lattice should be finite. However, I don't know how to generate all semi-lattices containing exactly $n-$elements.

However, if you need an arbitrary semi-lattice $L$ and a morphism $f$ of $L$ onto itself, then there is a method. Choose $n-$ many different sequences, say $c^i:=(c_{ij})_{j=1}^{\infty}$ satisfying $\sum_j c_{ij}=\infty$ for each $i=1\ldots n.$ Then define $T\colon \mathbb{K}^n\rightarrow \mathbb{K}^n$ by $$Tx_{i}:= \Sigma_{\gamma(j,k)=i} c_{jk} \wedge ((x_j-\Sigma_{s=0}^{k-1}c_{js})\vee 0)$$
where $\gamma$ is any function from $\{ 1,2,\ldots n\}\times \mathbb{N}$ into $\{1,2,\ldots,n\}.$ For arbitrary $n,$ the sequences $c_{ij}$ and the rule $\gamma$ should be chosen in such a way that a periodic point of the dynamical system $T\colon \mathbb{K}^n\rightarrow \mathbb{K}^n$ should be computable. I.e, you should choose these variables according to your purpose and $n$. Then a result of Scheutzow say that, the restriction of $T$ onto the semi-lattice generated by the orbit of this periodic point(it is finite) is a morphism.
The resource is "Admissible Arrays and a generalization of Perron-Frobenius theory" , Nussbaum & Scheutzow

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.