ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 24 Sep 2017 19:40:59 +0200Finding certain posets in SAGEhttps://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/ Distributive lattices can be characterised as lattices having no sublattice isomorphic to the diamond or the pentagon (see for example https://en.wikipedia.org/wiki/Distributive_lattice ). Now I try to obtain in SAGE all connected posets with a global maximum and a global minimum that do not contain the diamond or the pentagon as a subposet. How to do that in SAGE in the quickest possible way?
And do such (maybe not necessarily connected) posets have a name or are enumerated in the OEIS?Fri, 22 Sep 2017 01:33:51 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/Answer by dan_fulea for <p>Distributive lattices can be characterised as lattices having no sublattice isomorphic to the diamond or the pentagon (see for example <a href="https://en.wikipedia.org/wiki/Distributive_lattice">https://en.wikipedia.org/wiki/Distrib...</a> ). Now I try to obtain in SAGE all connected posets with a global maximum and a global minimum that do not contain the diamond or the pentagon as a subposet. How to do that in SAGE in the quickest possible way?
And do such (maybe not necessarily connected) posets have a name or are enumerated in the OEIS?</p>
https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?answer=38953#post-id-38953The oeis is here: [A006982](https://oeis.org/A006982)
The list appears in [M. Erné, J. Heitzig and J. Reinhold, On the number of distributive lattices, Electronic Journal of Combinatorics, 9 (2002), #R24.](https://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r24.pdf)
It is a highly combinatorial job to compute the numbers in the sequence.
Their strategy is to compute first the numbers of the vertically indecomposable, distributive lattices.
Which are lattices that cannot be decomposed as a vertical sum of at least two distributive lattices. The vertical sum of
$$(D_A;0_A,1_A;\le_A)$$
(placed in our minds vertically below) and
$$(D_B;0_A,1_A;\le_A)$$
(placed in our minds vertically above the previous structure)
is the lattice on the set $D=D_A\sqcup D_B/1_A\sim 0_B$ with $0=0_A$ and $1=1_B$ and the induced order that makes $D_A\le D_B$, elementwise.
Each distributive lattice appears **uniquely** as a vertical sum of vertically independent distributive lattices. The generating series for the vertically independent ones is:
$V(t) = t^2+t^4+t^6+3t^8+t^9+6t^{10}+2t^{11}+16t^{12}+8t^{13}+42t^{10}+28t^{15}+112t^{16}+\dots$
and form here on the numbers start to grow "also for the human eye in exponential taste". The coefficient in power $t^{49}$ is
$V_{49}= 5 045 200 597$. Having this list, we can generate the list for the distribute lattices, we will get
$$ D = \sum_{k\ge 0}D_kt^k$$
with $D_{49}=908 414 736 485 $.
At the level of enumeration, if we know the coefficients in $V$, then we can find the ones in $D$ simply. Let $W=V/t$. Then
$$D=t(1+V+V^2+\dots)=\frac t{1-V}$$
with computations in $\mathbb Z[[ t ]]$ . Sage code for this:
R.<t> = PolynomialRing( QQ )
V = ( t^2 + t^4 + t^6 + 3*t^8 + t^9
+ 6*t^10 + 2*t^11 + 16*t^12 + 8*t^13 + 42*t^14 + 28*t^15 + 112*t^16 + 93*t^17 + 311*t^18 + 295*t^19
+ 869*t^20 + 939*t^21 + 2454*t^22 + 2931*t^23 + 7032*t^24 + 9036*t^25 + 20301*t^26 + 27701*t^27 + 58929*t^28 + 84413*t^29
+ O(t^30) )
W = V/t
D = t/(1-W)
for c in D.coefficients():
print c
This gives:
1
1
1
2
3
5
8
15
26
47
82
151
269
494
891
1639
2978
5483
10006
18428
33749
62162
114083
210189
386292
711811
1309475
2413144
4442221
In accordance with [A006982](https://oeis.org/A006982).
So it is enough to write code that generates the vertically independent, distributive lattices.
I will try to do this till degree $64$ in the following days... This is then computing $D$ also till degree $64$.Sat, 23 Sep 2017 19:08:12 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?answer=38953#post-id-38953Comment by sagequstions for <p>The oeis is here: <a href="https://oeis.org/A006982">A006982</a></p>
<p>The list appears in <a href="https://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r24.pdf">M. Erné, J. Heitzig and J. Reinhold, On the number of distributive lattices, Electronic Journal of Combinatorics, 9 (2002), #R24.</a></p>
<p>It is a highly combinatorial job to compute the numbers in the sequence.</p>
<p>Their strategy is to compute first the numbers of the vertically indecomposable, distributive lattices.
Which are lattices that cannot be decomposed as a vertical sum of at least two distributive lattices. The vertical sum of
$$(D_A;0_A,1_A;\le_A)$$
(placed in our minds vertically below) and
$$(D_B;0_A,1_A;\le_A)$$
(placed in our minds vertically above the previous structure)
is the lattice on the set $D=D_A\sqcup D_B/1_A\sim 0_B$ with $0=0_A$ and $1=1_B$ and the induced order that makes $D_A\le D_B$, elementwise. </p>
<p>Each distributive lattice appears <strong>uniquely</strong> as a vertical sum of vertically independent distributive lattices. The generating series for the vertically independent ones is:
$V(t) = t^2+t^4+t^6+3t^8+t^9+6t^{10}+2t^{11}+16t^{12}+8t^{13}+42t^{10}+28t^{15}+112t^{16}+\dots$
and form here on the numbers start to grow "also for the human eye in exponential taste". The coefficient in power $t^{49}$ is
$V_{49}= 5 045 200 597$. Having this list, we can generate the list for the distribute lattices, we will get
$$ D = \sum_{k\ge 0}D_kt^k$$
with $D_{49}=908 414 736 485 $. </p>
<p>At the level of enumeration, if we know the coefficients in $V$, then we can find the ones in $D$ simply. Let $W=V/t$. Then
$$D=t(1+V+V^2+\dots)=\frac t{1-V}$$
with computations in $\mathbb Z[[ t ]]$ . Sage code for this:</p>
<pre><code>R.<t> = PolynomialRing( QQ )
V = ( t^2 + t^4 + t^6 + 3*t^8 + t^9
+ 6*t^10 + 2*t^11 + 16*t^12 + 8*t^13 + 42*t^14 + 28*t^15 + 112*t^16 + 93*t^17 + 311*t^18 + 295*t^19
+ 869*t^20 + 939*t^21 + 2454*t^22 + 2931*t^23 + 7032*t^24 + 9036*t^25 + 20301*t^26 + 27701*t^27 + 58929*t^28 + 84413*t^29
+ O(t^30) )
W = V/t
D = t/(1-W)
for c in D.coefficients():
print c
</code></pre>
<p>This gives:</p>
<pre><code>1
1
1
2
3
5
8
15
26
47
82
151
269
494
891
1639
2978
5483
10006
18428
33749
62162
114083
210189
386292
711811
1309475
2413144
4442221
</code></pre>
<p>In accordance with <a href="https://oeis.org/A006982">A006982</a>.</p>
<p>So it is enough to write code that generates the vertically independent, distributive lattices.</p>
<p>I will try to do this till degree $64$ in the following days... This is then computing $D$ also till degree $64$.</p>
https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38954#post-id-38954Thank you for your answer.
Sorry im confused. Do you enumerate the distributive lattices here? My question was about connected posets with top and buttom that do not contain the pentagon and the diamond, which should be more general than distributive lattice (the lattice property is not included).Sat, 23 Sep 2017 19:24:16 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38954#post-id-38954Comment by dan_fulea for <p>The oeis is here: <a href="https://oeis.org/A006982">A006982</a></p>
<p>The list appears in <a href="https://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r24.pdf">M. Erné, J. Heitzig and J. Reinhold, On the number of distributive lattices, Electronic Journal of Combinatorics, 9 (2002), #R24.</a></p>
<p>It is a highly combinatorial job to compute the numbers in the sequence.</p>
<p>Their strategy is to compute first the numbers of the vertically indecomposable, distributive lattices.
Which are lattices that cannot be decomposed as a vertical sum of at least two distributive lattices. The vertical sum of
$$(D_A;0_A,1_A;\le_A)$$
(placed in our minds vertically below) and
$$(D_B;0_A,1_A;\le_A)$$
(placed in our minds vertically above the previous structure)
is the lattice on the set $D=D_A\sqcup D_B/1_A\sim 0_B$ with $0=0_A$ and $1=1_B$ and the induced order that makes $D_A\le D_B$, elementwise. </p>
<p>Each distributive lattice appears <strong>uniquely</strong> as a vertical sum of vertically independent distributive lattices. The generating series for the vertically independent ones is:
$V(t) = t^2+t^4+t^6+3t^8+t^9+6t^{10}+2t^{11}+16t^{12}+8t^{13}+42t^{10}+28t^{15}+112t^{16}+\dots$
and form here on the numbers start to grow "also for the human eye in exponential taste". The coefficient in power $t^{49}$ is
$V_{49}= 5 045 200 597$. Having this list, we can generate the list for the distribute lattices, we will get
$$ D = \sum_{k\ge 0}D_kt^k$$
with $D_{49}=908 414 736 485 $. </p>
<p>At the level of enumeration, if we know the coefficients in $V$, then we can find the ones in $D$ simply. Let $W=V/t$. Then
$$D=t(1+V+V^2+\dots)=\frac t{1-V}$$
with computations in $\mathbb Z[[ t ]]$ . Sage code for this:</p>
<pre><code>R.<t> = PolynomialRing( QQ )
V = ( t^2 + t^4 + t^6 + 3*t^8 + t^9
+ 6*t^10 + 2*t^11 + 16*t^12 + 8*t^13 + 42*t^14 + 28*t^15 + 112*t^16 + 93*t^17 + 311*t^18 + 295*t^19
+ 869*t^20 + 939*t^21 + 2454*t^22 + 2931*t^23 + 7032*t^24 + 9036*t^25 + 20301*t^26 + 27701*t^27 + 58929*t^28 + 84413*t^29
+ O(t^30) )
W = V/t
D = t/(1-W)
for c in D.coefficients():
print c
</code></pre>
<p>This gives:</p>
<pre><code>1
1
1
2
3
5
8
15
26
47
82
151
269
494
891
1639
2978
5483
10006
18428
33749
62162
114083
210189
386292
711811
1309475
2413144
4442221
</code></pre>
<p>In accordance with <a href="https://oeis.org/A006982">A006982</a>.</p>
<p>So it is enough to write code that generates the vertically independent, distributive lattices.</p>
<p>I will try to do this till degree $64$ in the following days... This is then computing $D$ also till degree $64$.</p>
https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38957#post-id-38957The equivalence holds *for lattices*
[https://en.wikipedia.org/wiki/Distributive_lattice](https://en.wikipedia.org/wiki/Distributive_lattice#Characteristic_properties)
where they claim
*A lattice is distributive if and only if none of its sublattices is isomorphic to $M_3$ or $N_5$.*
(My relation to this field of research is rather tangential. The only intersection is related to standard tableaux and the corresponding order.)
Let $X$ with existing $0=\min X$ and $1=\max X$ be a poset without pentagons as subposets. Assume $a,b\in X$ have two different least upper bounds $s,t$. Then the subposet with elements $0;a,s;b;1$ is a pentagon. Contradiction. So the supremum of $(a,b)$ exists, since $1$ is an upper bound. Same / dually for infimum.
Is this ok?!Sat, 23 Sep 2017 20:19:50 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38957#post-id-38957Comment by sagequstions for <p>The oeis is here: <a href="https://oeis.org/A006982">A006982</a></p>
<p>The list appears in <a href="https://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r24.pdf">M. Erné, J. Heitzig and J. Reinhold, On the number of distributive lattices, Electronic Journal of Combinatorics, 9 (2002), #R24.</a></p>
<p>It is a highly combinatorial job to compute the numbers in the sequence.</p>
<p>Their strategy is to compute first the numbers of the vertically indecomposable, distributive lattices.
Which are lattices that cannot be decomposed as a vertical sum of at least two distributive lattices. The vertical sum of
$$(D_A;0_A,1_A;\le_A)$$
(placed in our minds vertically below) and
$$(D_B;0_A,1_A;\le_A)$$
(placed in our minds vertically above the previous structure)
is the lattice on the set $D=D_A\sqcup D_B/1_A\sim 0_B$ with $0=0_A$ and $1=1_B$ and the induced order that makes $D_A\le D_B$, elementwise. </p>
<p>Each distributive lattice appears <strong>uniquely</strong> as a vertical sum of vertically independent distributive lattices. The generating series for the vertically independent ones is:
$V(t) = t^2+t^4+t^6+3t^8+t^9+6t^{10}+2t^{11}+16t^{12}+8t^{13}+42t^{10}+28t^{15}+112t^{16}+\dots$
and form here on the numbers start to grow "also for the human eye in exponential taste". The coefficient in power $t^{49}$ is
$V_{49}= 5 045 200 597$. Having this list, we can generate the list for the distribute lattices, we will get
$$ D = \sum_{k\ge 0}D_kt^k$$
with $D_{49}=908 414 736 485 $. </p>
<p>At the level of enumeration, if we know the coefficients in $V$, then we can find the ones in $D$ simply. Let $W=V/t$. Then
$$D=t(1+V+V^2+\dots)=\frac t{1-V}$$
with computations in $\mathbb Z[[ t ]]$ . Sage code for this:</p>
<pre><code>R.<t> = PolynomialRing( QQ )
V = ( t^2 + t^4 + t^6 + 3*t^8 + t^9
+ 6*t^10 + 2*t^11 + 16*t^12 + 8*t^13 + 42*t^14 + 28*t^15 + 112*t^16 + 93*t^17 + 311*t^18 + 295*t^19
+ 869*t^20 + 939*t^21 + 2454*t^22 + 2931*t^23 + 7032*t^24 + 9036*t^25 + 20301*t^26 + 27701*t^27 + 58929*t^28 + 84413*t^29
+ O(t^30) )
W = V/t
D = t/(1-W)
for c in D.coefficients():
print c
</code></pre>
<p>This gives:</p>
<pre><code>1
1
1
2
3
5
8
15
26
47
82
151
269
494
891
1639
2978
5483
10006
18428
33749
62162
114083
210189
386292
711811
1309475
2413144
4442221
</code></pre>
<p>In accordance with <a href="https://oeis.org/A006982">A006982</a>.</p>
<p>So it is enough to write code that generates the vertically independent, distributive lattices.</p>
<p>I will try to do this till degree $64$ in the following days... This is then computing $D$ also till degree $64$.</p>
https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38958#post-id-38958I have no experience with posets or lattice, I am more or less just interesting in homological things related to incidence algebras. So I might do stupid things here. I thought I had a poset with top and bottum without pentagon or diamond poset that is not a lattice, but of course I might have a thinking error. I do not see a pentagon in 0;a,s;b;1, shouldnt it look like number 6 in http://math.chapman.edu/~jipsen/tikzsvg/planar-distributive-lattices15.html ?Sat, 23 Sep 2017 20:52:56 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38958#post-id-38958Comment by dan_fulea for <p>The oeis is here: <a href="https://oeis.org/A006982">A006982</a></p>
<p>The list appears in <a href="https://www.emis.de/journals/EJC/Volume_9/PDF/v9i1r24.pdf">M. Erné, J. Heitzig and J. Reinhold, On the number of distributive lattices, Electronic Journal of Combinatorics, 9 (2002), #R24.</a></p>
<p>It is a highly combinatorial job to compute the numbers in the sequence.</p>
<p>Their strategy is to compute first the numbers of the vertically indecomposable, distributive lattices.
Which are lattices that cannot be decomposed as a vertical sum of at least two distributive lattices. The vertical sum of
$$(D_A;0_A,1_A;\le_A)$$
(placed in our minds vertically below) and
$$(D_B;0_A,1_A;\le_A)$$
(placed in our minds vertically above the previous structure)
is the lattice on the set $D=D_A\sqcup D_B/1_A\sim 0_B$ with $0=0_A$ and $1=1_B$ and the induced order that makes $D_A\le D_B$, elementwise. </p>
<p>Each distributive lattice appears <strong>uniquely</strong> as a vertical sum of vertically independent distributive lattices. The generating series for the vertically independent ones is:
$V(t) = t^2+t^4+t^6+3t^8+t^9+6t^{10}+2t^{11}+16t^{12}+8t^{13}+42t^{10}+28t^{15}+112t^{16}+\dots$
and form here on the numbers start to grow "also for the human eye in exponential taste". The coefficient in power $t^{49}$ is
$V_{49}= 5 045 200 597$. Having this list, we can generate the list for the distribute lattices, we will get
$$ D = \sum_{k\ge 0}D_kt^k$$
with $D_{49}=908 414 736 485 $. </p>
<p>At the level of enumeration, if we know the coefficients in $V$, then we can find the ones in $D$ simply. Let $W=V/t$. Then
$$D=t(1+V+V^2+\dots)=\frac t{1-V}$$
with computations in $\mathbb Z[[ t ]]$ . Sage code for this:</p>
<pre><code>R.<t> = PolynomialRing( QQ )
V = ( t^2 + t^4 + t^6 + 3*t^8 + t^9
+ 6*t^10 + 2*t^11 + 16*t^12 + 8*t^13 + 42*t^14 + 28*t^15 + 112*t^16 + 93*t^17 + 311*t^18 + 295*t^19
+ 869*t^20 + 939*t^21 + 2454*t^22 + 2931*t^23 + 7032*t^24 + 9036*t^25 + 20301*t^26 + 27701*t^27 + 58929*t^28 + 84413*t^29
+ O(t^30) )
W = V/t
D = t/(1-W)
for c in D.coefficients():
print c
</code></pre>
<p>This gives:</p>
<pre><code>1
1
1
2
3
5
8
15
26
47
82
151
269
494
891
1639
2978
5483
10006
18428
33749
62162
114083
210189
386292
711811
1309475
2413144
4442221
</code></pre>
<p>In accordance with <a href="https://oeis.org/A006982">A006982</a>.</p>
<p>So it is enough to write code that generates the vertically independent, distributive lattices.</p>
<p>I will try to do this till degree $64$ in the following days... This is then computing $D$ also till degree $64$.</p>
https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38966#post-id-38966Yes, my argument above is false, an error, $s$ is connected to both $a$ and $b$. But if we allow configurations like
1
/ \
s t
|\ /|
| \ |
|/ \|
a b
\ /
0
then the world becomes very rich! Even if we assume a level structure, the combinatorial data between levels may become very complicated. At this point i have no idea how to sort the structure...Sun, 24 Sep 2017 19:40:59 +0200https://ask.sagemath.org/question/38938/finding-certain-posets-in-sage/?comment=38966#post-id-38966