# Finding posets of a certain form 2

I try to obtain the connected posets with n elements having a top and bottom such that in the Hasse quiver, in every point there start at most two arrows and at every point there end at most two arrows (thus for example all distributive lattices are of this form). Is there a quick command to obtain this as a list? What condition does one has to add in

posets = [ p for p in Posets(n) if p.is_connected() and p.has_top() and p.has_bottom()]


Actually a quick method would be cool which works up to n=10 or 11. (filtering things out of the set of all posets, seems to be very slow in SAGE)

edit retag close merge delete

By Hasse quiver, do you mean Hasse diagram?

If so, then you may use the DiGraph methods on the diagram to check the out-degree and the in-degree. See for example out_degree and in_degree.

( 2017-09-24 16:09:02 -0500 )edit

@fidbc Yes I mean the Hasse diagram. Thank I will look at it. But it is also important that the code is quick, so maybe filtering is not the quickest thing to do?

( 2017-09-24 16:15:59 -0500 )edit

This looks like a very particular set of posets. Maybe you'll need to generate them manually if you do not want to filter from the list of all posets.

( 2017-09-24 16:31:52 -0500 )edit

Depending on what you are planning to do with these posets, it might be worth filtering them up to a certain size and store the output. So that you can just go back and read from the stored list. However, if you are interested in say, counting them, then maybe generating them will be the way to go.

( 2017-09-24 16:34:55 -0500 )edit

First, isn't is_connected redundant once you know that p.has_top() is true? Second, it would probably be faster to construct all posets with n-2 elements and then adjoin a new top and bottom. Finally, do you need all of them at once? Note that posets = (p for p in Posets(5) ...) is much faster than the same with square brackets, and you can do for p in posets: ... just as well in either case.

( 2017-09-28 17:05:49 -0500 )edit

Sort by » oldest newest most voted

The following code collects the directed graphs associated to Hasse diagrams for the specified posets.

I hope the recursion works as needed. However, the code does not perform well up to 10 or 11 vertices...

class MyDiGraph( DiGraph ):
"""class extending DiGraph
"""

def __init__( self, *args, **kargs ):
super( MyDiGraph, self ).__init__( *args, **kargs )
self.open_valence_dic = {}

def add_top_joins( self, n, jList ):
"""
add the vertex n and an edge j -> n for each j in jList
also set the open valence 2 for the new vertex n
"""

for j in jList:
self . add_edges( [ (j,n) ] )
self . open_valence_dic[j] -= 1
self . open_valence_dic[n] = 2

def is_valid_final_hasse_diagram( self ):
n = max( self.vertices() )
A = matrix.identity( ZZ, n ) + self.adjacency_matrix()
An = A^n
if min( list( An.row(0) ) + list( An.column(n-1) ) ) > 0:
return True
return False

import copy

def compute_MyDiGraph_List( level=1, verbose=False ):
"""recursively comute all MyDiGraph instances up to isomorphism.
"""

if level not in ZZ or level < 0:
return []

n = 0
while n < level:
n += 1
if verbose:
print "LEVEL", n
if n == 1:
D = MyDiGraph( { 1: [] }
, weighted=False
, format='dict_of_lists' )
D.open_valence_dic[1] = 2
newList = [ D, ]
else:
oldList = newList[:]
newList = []    # and we append
for oldD in oldList:
open_vertices = [ j
for j in oldD.vertices()
if oldD.open_valence_dic[j] > 0 ]
for j in open_vertices:
D = copy.deepcopy( oldD )
D . add_top_joins( n, [j,] )
newList.append( D )
for k in open_vertices:
if k <= j:
continue

DD = copy.deepcopy( D )
DD . add_top_joins( n, [k,] )
newList.append( DD )
if verbose:
print "\t%s new digraphs" % len( newList )
isoList = []
for D in newList:
ok = True
for iD in isoList:
if D.is_isomorphic( iD ):
ok = False
break
if ok:
isoList.append(D)
newList = isoList[:]
if verbose:
print "\t%s new digraphs up to isomorphism\n" % len( newList )

return [ D
for D in newList
if D.is_valid_final_hasse_diagram()  ]

digraphs = compute_MyDiGraph_List( level=8, verbose=True )

print len(digraphs)


The above runs in verbose mode and shows information about the collected data:

LEVEL 1
1 new digraphs
1 new digraphs up to isomorphism

LEVEL 2
1 new digraphs
1 new digraphs up to isomorphism

LEVEL 3
3 new digraphs
3 new digraphs up to isomorphism

LEVEL 4
12 new digraphs
9 new digraphs up to isomorphism

LEVEL 5
52 new digraphs
36 new digraphs up to isomorphism

LEVEL 6
265 new digraphs
169 new digraphs up to isomorphism

LEVEL 7
1527 new digraphs
922 new digraphs up to isomorphism

LEVEL 8
9946 new digraphs
5696 new digraphs up to isomorphism

2143


Some comments on the last data for the last level. The code collected first 9946 digraphs on 8 vertices, that would be possibly relevant for the next step. Among them, after a time consuming process, there are only 5696 such digraphs up to isomorphism. The recursion constructs digraphs such that each new top node $n$ is connected with at least one node among $1,2,\dots,(n-1)$. So this insures the existence of a path to the minimal vertex $1$. But there be no path to the new top, $n$. Among the $5696$ digraphs there are $2143$ digraphs, such that each vertex lies at at least one path from $1$ to $n=8$.

After the design was established and the results are now here, one can draw conclusions and make things better. Perhaps the deep copy operations are time consuming. A better strategy would be now to work with upper diagonal zero-one-matrices next time, at least as long we are generating the new generation of matrices. Only the check for isomorphisms must be maybe done in the digraph world. For instance it should be simpler to store and extend the data

sage: D = digraphs[99]

[0 1 1 0 0 0 0 0]
[0 0 0 1 1 0 0 0]
[0 0 0 0 0 1 1 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0]


than doing this with the corresponding digraph. The condition

        if min( list( An.row(0) ) + list( An.column(n-1) ) ) > 0:
return True


is very pessimistic. In fact it is a slow condition, the first row has by construction only elements $\ge 1$, so i think we can write simpler if min( list( An.column(n-1) ) ) > 0: and possibly there is no need to use the matrix A, since the dictionary of valencies still open for higher levels to come has the information. But i am in time troubles, have to stop here.

more