Random connected poset on n elements

[Christian Stump]

Is there a way to obtain a random connected poset on n unlabelled elements in sage?

Random preferably means uniformly at random, but other randomness might be okay if it is not too far away from uniform. Generating all posets, checking for connectedness and picking is way too slow.

Equivalently, what about random connected acyclic graphs ?

I find

sage: from sage.graphs.graph_generators_pyx import RandomGNP
sage: D = RandomGNP(10, .2, directed = True)

but this ignores connected (not too bad) and acyclic (bad), and doesn't seeem to be close is not even close to uniformly at random.

Thanks, Christian

[Dima Pasechnik]

I would have done the following:

0) take a connected random graph (call graphs.RandomGNP in a loop, until you get something connected)

1) take a random ordering of vertices, say v1,v2,...,vn.

2) orient each edge (vi,vj) in the direction j>i.

While this might not be uniform on the probability space of acyclic orientations,

perhaps it's good enough for your purposes.

[Christian Stump]

0) take a connected random graph (call graphs.RandomGNP in a loop, until you get something connected)

1) take a random ordering of vertices, say v1,v2,...,vn.

2) orient each edge (vi,vj) in the direction j>i.

This last step is actually a good idea, I didn't think of this way of getting a somewhat random acyclic orientation -- I'll try playing, thanks!

[Jori Mäntysalo]

On Thu, 30 Nov 2017, Christian Stump wrote:

> Is there a way to obtain a random connected poset on n unlabelled elements in sage?

How big is your n?

"Almost all" finite posets are connected, so uniform distribution of all
posets would work too for bigger n.

--
Jori Mäntysalo

[Christian Stump]

How big is your n?

not very big, I aim for the biggest n for which I can loop through all permutations of n and compute some numbers. I expect this to be between 10 and 14.

 

"Almost all" finite posets are connected, so uniform distribution of all posets would work too for bigger n.

how would I get uniform distribution on all posets?

[Jori Mäntysalo]

On Thu, 30 Nov 2017, Christian Stump wrote:

I meant that it won't help you to discard unconnected ones.

There is a code for generating posets, see attachment at
https://trac.sagemath.org/ticket/14110 , but unfortunately it has not been
integrated to Sage. I just tested and it takes about 2,2 seconds to
generate 11-element posets (there are 46749427 of those) and 38 seconds
for 12-element posets. I guess you could use that up to 14 elements.

--
Jori Mäntysalo

[Christian Stump]

There is a code for generating posets, see attachment at
https://trac.sagemath.org/ticket/14110 , but unfortunately it has not been
integrated to Sage. I just tested and it takes about 2,2 seconds to
generate 11-element posets (there are 46749427 of those) and 38 seconds
for 12-element posets. I guess you could use that up to 14 elements.

that's indeed a good pointer, that might indeed work!