Ask Your Question
0

Lattice of maximum-length antichains in sage

asked 2025-02-05 19:57:43 +0100

sagequstions gravatar image

updated 2025-02-07 06:21:59 +0100

Max Alekseyev gravatar image

The Dilworth lattice of a poset $P$ is the lattice of maximum length antichains in $P$, where two such antichains have $A \leq B$ if and only if every member of $A$ is less than or equal to some member of $B$.

Question: Is there an easy way to obtain the Dilworth lattice of a given poset using Sage?

Here my attempt:

P=posets.PentagonPoset()
A = P.antichains()
O=Poset((A,lambda v,w:v<=w))

I do not know how to define the right order on A in an easy way. It seems that <= is the wrong order, but even then it gives an error.

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
2

answered 2025-02-07 11:54:08 +0100

FrédéricC gravatar image

updated 2025-02-07 13:11:07 +0100

Like this

def dilworth(P):
    def lequal(A, B):
        return all(any(P.is_lequal(a, b) for b in B) for a in A)
    w = P.width()
    data = [tuple(a) for a in P.maximal_antichains() if len(a) == w]
    return Poset([data, lequal])
edit flag offensive delete link more
1

answered 2025-02-05 21:50:46 +0100

JTS gravatar image

Here is my attempt:

def smallerB(a,B,P):
if len([b for b in B if P.is_lequal(a,b)]) > 0:
    return true
else:
    return false

def smallerP(A,B,P):
      if len(A) == len([a for a in A if smallerB(a,B,P)]):
          return true
      else:
          return false

def dilworth(P):
    ANTI = [Set(_) for _ in P.antichains()]
    maxl = max([len(_) for _ in ANTI])
    MANTI = [_ for _ in ANTI if len(_) == maxl]
    RELS = [[A,B] for A in MANTI for B in MANTI if smallerP(A,B,P)]
    Q = Poset((MANTI, RELS))
    return Q

Now test it:

   P = Poset(([1,2,3,4,5], [[0, 2], [1, 2], [1, 3], [2, 5], [3, 4], [3, 5]]))
   Q = dilworth(P)
   P.plot()
   Q.plot()

Poset P Poset Q

I might have misunderstood your definition of the Dilworth lattice, so chek my work!

edit flag offensive delete link more

Comments

One can replace P.antichains() with P.maximal_antichains() since each maximum-length antichain is also maximal.

Max Alekseyev gravatar imageMax Alekseyev ( 2025-02-05 22:49:34 +0100 )edit

False and True should take capitals

FrédéricC gravatar imageFrédéricC ( 2025-02-07 08:15:35 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2025-02-05 19:57:43 +0100

Seen: 117 times

Last updated: Feb 07