In the different courses, we have heard a lot about partially ordered set or posets. They are implemented in Sage, we will run through some examples and see if we can reproduce the results of the class.
They are many options to construct a poset in Sage.
First, you can give a dictionary
In [1]:
d = {1:[2,3], 2:[4], 3:[4]}
P = Poset(d); P
For each element $x$ of the poset, you give the lists of $y$ such that $x$ is covered by $y$.
If you give relations that are not cover relations, it still works.
In [2]:
d = {1:[2,3,4], 2:[4], 3:[4]}
PP = Poset(d); PP
Another way is to give a comparision function of the elements.
In [3]:
D = list(divisors(12))
P1 = Poset([D, lambda i,j : i.divides(j)]); P1
To declare the function, you use the keyword lambda then $x$ and $y$ are elements of the poset and you write an expression which is True if $x \leq y$ in the poset. In the example above, $x \leq y$ iif $x$ divides $y$.
Yon can also give a function that describes only the cover relations.
In [4]:
D = list(divisors(12))
P1 = Poset([D, lambda i,j : i.divides(j) and (j//i).is_prime()], cover_relations=True); P1
Another way is to give the list of elements and a list of relations. For example
In [2]:
P1 = Poset([list(divisors(12)), [(1,2),(1,3),(2,4),(2,6),(3,6),(4,12),(6,12)]])
P1
If the relations you give create a cycle (which means the poset is not antisymmetric), this creates an error.
In [1]:
P2 = Poset([[1,2,3], [(1,2),(2,3),(3,1)]])
Once the poset is created, you can see the available methods by typing P1. + tab key.
In [ ]:
P1. # place the cursor after the dot and type the tab key
For example, you can check that the poset is a lattice.
In [8]:
P1.is_lattice()
Or if it's ranked.
In [9]:
P1.is_ranked()
You can even get its rank function.
In [5]:
f = P1.rank_function()
In [9]:
f(1)
In [10]:
f(2)
In [11]:
f(3)
In [12]:
f(4)
In [13]:
f(6)
In [14]:
f(12)
Sage can construct all subsets of a certain set.
In [16]:
Sub4 = Subsets([1,2,3,4])
Sub4
In [18]:
list(Sub4)
You can create a specific subset the following way:
In [24]:
s1 = Sub4({1,2})
s2 = Sub4({2,3,4})
You can test if a subset is included in another one using this method:
In [28]:
s1.issubset(s2)
In [29]:
s3 = Sub4({1})
s3.issubset(s1)
Exercise Create the poset of the subsets of $2^{[4]}$.
In [17]:
Is it a lattice? (Let Sage tell you)
In [18]:
Is it gradded?
In [19]:
Compute the rank function of the subset \lbrace 1,2,3 \rbrace
In [20]:
Use Sage to compute the number of elements of each rank and check the properties seen in the class (for example, the alternating sum)
In [22]:
In [34]:
p = PermutationGroupElement([(1,2,3,4)]) # create the cyclic permutation
In [35]:
G = PermutationGroup([p]) # create the group generated by that element
G
In [31]:
list(G)
If you have a subset, you can compute its images by the elements of the group.
In [38]:
s = Sub4({1,2})
orbit = []
for p in G:
orbit.append(Sub4({p(i) for i in s}))
print orbit
We can create the list of all orbits.
In [47]:
Orbits = []
S = set(Sub4) # we compute all the elements
while len(S) > 0:
s = S.pop() # we take one element out
orbit = set()
for p in G:
orbit.add(Sub4({p(i) for i in s})) # we add the image to the orbit
S.difference_update(orbit) # we remote the elements of the orbit from the initial set
Orbits.append(tuple(orbit)) # note : we transform them into type "tuple" so that they are "immutable"
Orbits
Exercise complete the code of the following function to compare orbits.
In [48]:
def orbit_comp(o1, o2):
"""
Return true if at least one element of o1 is smaller than one elements of o2
"""
# edit here
Does it work?
In [49]:
orbit_comp(Orbits[0], Orbits[1]) # should say True
In [50]:
orbit_comp(Orbits[0], Orbits[2]) # should say False
In [51]:
POrbits = Poset([Orbits, lambda x,y: orbit_comp(x,y)])
POrbits
Using similar methods, construct the poset of $2^{[6]}$ quotiented by the cyclic group. Then check the properties that we have seen in class.
In [ ]:
In [53]:
In [ ]: