Join operation in arbitrary poset

[Robin van der veer]

Hello,

I wonder if there is any way to use the join or meet operations in arbitrary posets? 

It seems that these methods are only exposed in the classes of join- resp. meet semilattices.

However, it would be very convenient if these methods were available in general posets somehow, and would just raise an exception if the join/meet does not exist.

The problem that I'm facing now is that the posets I'm working with are not join semilattices, but it is essential for me to compute joins of certain subsets anyway (these join do exist).

Since the join semilattice constructor verifies that the poset is actually a join semilattice (and from what I see this validation cannot be disabled), I cannot construct my posets as join semilattices and use the join method.

Any suggestions on how to go about it? Or is the only solution to just implement a join operation myself?

Thanks

[Jori Mantysalo]

On Mon, 3 Apr 2017, Robin van der veer wrote:

> I wonder if there is any way to use the join or meet operations in arbitrary
> posets? 

How fast that should be? The trivial implementation is just 4 lines long,
here with monkey patch:

def join2(self, a, b):
j = self.subposet([e for e in self.principal_upper_set(a) if e in self.principal_upper_set(b)])
if len(j) > 1:
raise ValueError("no join for %s and %s" % (a, b))
return j[0]
type(Poset()).join = join2

P = Poset({1:[3, 4], 2:[3, 4], 3:[5], 4:[5]})
P.join(3, 4)

It sounds a little unnatural to have join or meet for all posets. Other
users might except L.join() to return an error if L is not a
join-semilattice.

--
Jori Mäntysalo

[Robin van der veer]

Thanks for your reply.

To me the essence of the definition of join and meetsemilattice is about joins/meets existing for ALL pairs, as opposed to some pairs. Hence having a join/meet operation on any poset is not that unnatural, because almost all posets have at least some pairs of element for which the join/meet exists (e.g. trivial pairs x<= y). 

I am actually porting some code that I wrote in Macaulay2 to Sage, because of Sage's way better support for matroids. In Macaulay2 joins/meets are implemented for all posets. I think what I'll do is just use Sage for its matroid library, and output the posets I need to Macaulay2 for further processing.

As for your code, I think you want to return j.bottom(), not just the first element of j, correct? Either way I'm not sure that this is efficient enough to be workable, but I will try it. 

Op dinsdag 4 april 2017 06:01:48 UTC+2 schreef jori.ma...@uta.fi:

[Jori Mantysalo]

On Tue, 4 Apr 2017, Robin van der veer wrote:

> Thanks for your reply.To me the essence of the definition of join and meetsemilattice is about joins/meets existing for ALL

> pairs, as opposed to some pairs.

As a slow code you can just say something like

Matrix([join2(L, a, b) for a in L] for b in L])

> As for your code, I think you want to return j.bottom(), not just the first element of j, correct?

Actually it is the same thing, as for any poset P in Sage we have P[0],
P[1], ... a linear extension of P.

> Either way I'm not sure that this is efficient enough to be workable,
> but I will try it. 

It should be quite easy to make faster one for bigger posets. OTOH Sage is
about never very fast compared to C code, when your computation has
for-loops. But then, nowadays computers are so fast that even "slow" code
is often fast.

--
Jori Mäntysalo

[Robin van der veer]

I similar "problem": atoms() is not implemented for the MeetSemilattice, while it certainly makes sense there.

Op maandag 3 april 2017 23:57:44 UTC+2 schreef Robin van der veer:

[Jori Mantysalo]

On Tue, 4 Apr 2017, Robin van der veer wrote:

> I similar "problem": atoms() is not implemented for the MeetSemilattice,
> while it certainly makes sense there.

Good point. I opened https://trac.sagemath.org/ticket/22757 for that.

--
Jori Mäntysalo