Checking for indepenedent sets in a bipartite graph with equal number of odd and even elements in SageMath

Question

By using the IndependentSets module in SageMath, we can list all the independent sets of a graph. Suppose I have a bipartite graph on the Symmetric Group with partite sets consisting of even and odd permutations.

How do I enumerate and list out all those independent sets which consists of equal number of elements from even and odd permutations. What all methods and functions do I need to use. Is there some built in function for listing the type of a symmetric group element as even or odd.

My idea of pseudo-code idea would be:

G=SymmetricGroup(4)
CG = G.cayley_graph(generators=[G((1,2)),G((1,3)),G((1,4)),G((2,3)),G((2,4)),G((3,4))])
CGU = CG.to_undirected()
I=IndependentSets(CGU)
for list in I:
   for i in list:
       if enumerate(type(list[i])=='even')==enumerate(type(list[i]=='odd'):
add list in list1

print(list1)

However, I encountered the error that list indices must be integers or slices and not permutation group elements. How do rectify this? Any hints?

Answer 1

Try this:

from sage.graphs.independent_sets import IndependentSets
S = SymmetricGroup(3) # Or whatever you want.
P1 = [S((1, 2)), S((1, 3)), S((2, 3))] # Two parts of the partition,
P2 = [S((1,2,3)), S((1,3,2)), S(())]   # adjust these as you want.
G = BipartiteGraph([P1,P2])
I = IndependentSets(G)
L = []
for l in I:
    if (sum(x.sign()==1 for x in l) == sum(x.sign()==-1 for x in l)):
        L.append(l)
print(L)

or slightly more efficiently, replace the third last line with

    if (sum(x.sign() for x in l) == 0):