Perfect matchings

A perfect matching of a set \(S\) is a partition into 2-element sets. If \(S\) is the set \(\{1,...,n\}\), it is equivalent to fixpoint-free involutions. These simple combinatorial objects appear in different domains such as combinatorics of orthogonal polynomials and of the hyperoctaedral groups (see [MV], [McD] and also [CM]):

AUTHOR:

• Valentin Feray, 2010 : initial version

• Martin Rubey, 2017: inherit from SetPartition, move crossings and nestings to SetPartition

EXAMPLES:

Create a perfect matching:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')]);m
[('a', 'e'), ('b', 'c'), ('d', 'f')]

Count its crossings, if the ground set is totally ordered:

sage: n = PerfectMatching([3,8,1,7,6,5,4,2]); n
[(1, 3), (2, 8), (4, 7), (5, 6)]
sage: n.number_of_crossings()
1

List the perfect matchings of a given ground set:

sage: PerfectMatchings(4).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]

REFERENCES:

MV

combinatorics of orthogonal polynomials (A. de Medicis et X.Viennot, Moments des q-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math., 15 (1994), 262-304)

McD

combinatorics of hyperoctahedral group, double coset algebra and zonal polynomials (I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, second edition, 1995, chapter VII).

CM(1,2,3)

Benoit Collins, Sho Matsumoto, On some properties of orthogonal Weingarten functions, arXiv 0903.5143.

class sage.combinat.perfect_matching.PerfectMatching(parent, s, check=True, sort=True)

Bases: sage.combinat.set_partition.SetPartition

A perfect matching.

A perfect matching of a set \(X\) is a set partition of \(X\) where all parts have size 2.

A perfect matching can be created from a list of pairs or from a fixed point-free involution as follows:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')]);m
[('a', 'e'), ('b', 'c'), ('d', 'f')]
sage: n = PerfectMatching([3,8,1,7,6,5,4,2]);n
[(1, 3), (2, 8), (4, 7), (5, 6)]
sage: isinstance(m,PerfectMatching)
True

The parent, which is the set of perfect matchings of the ground set, is automatically created:

sage: n.parent()
Perfect matchings of {1, 2, 3, 4, 5, 6, 7, 8}

If the ground set is ordered, one can, for example, ask if the matching is non crossing:

sage: PerfectMatching([(1, 4), (2, 3), (5, 6)]).is_noncrossing()
True

Weingarten_function(d, other=None)

Return the Weingarten function of two pairings.

This function is the value of some integrals over the orthogonal groups \(O_N\). With the convention of [CM], the method returns \(Wg^{O(d)}(other,self)\).

EXAMPLES:

sage: var('N')
N
sage: m = PerfectMatching([(1,3),(2,4)])
sage: n = PerfectMatching([(1,2),(3,4)])
sage: factor(m.Weingarten_function(N,n))
-1/((N + 2)*(N - 1)*N)

loop_type(other=None)

Return the loop type of self.

INPUT:

• other – a perfect matching of the same set of self. (if the second argument is empty, the method an_element() is called on the parent of the first)

OUTPUT:

If we draw the two perfect matchings simultaneously as edges of a graph, the graph obtained is a union of cycles of even lengths. The function returns the ordered list of the semi-length of these cycles (considered as a partition)

EXAMPLES:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')])
sage: n = PerfectMatching([('a','b'),('d','f'),('e','c')])
sage: m.loop_type(n)
[2, 1]

loops(other=None)

Return the loops of self.

INPUT:

• other – a perfect matching of the same set of self. (if the second argument is empty, the method an_element() is called on the parent of the first)

OUTPUT:

If we draw the two perfect matchings simultaneously as edges of a graph, the graph obtained is a union of cycles of even lengths. The function returns the list of these cycles (each cycle is given as a list).

EXAMPLES:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')])
sage: n = PerfectMatching([('a','b'),('d','f'),('e','c')])
sage: loops = m.loops(n)
sage: loops # random
[['a', 'e', 'c', 'b'], ['d', 'f']]

sage: o = PerfectMatching([(1, 7), (2, 4), (3, 8), (5, 6)])
sage: p = PerfectMatching([(1, 6), (2, 7), (3, 4), (5, 8)])
sage: o.loops(p)
[[1, 7, 2, 4, 3, 8, 5, 6]]

loops_iterator(other=None)

Iterate through the loops of self.

INPUT:

• other – a perfect matching of the same set of self. (if the second argument is empty, the method an_element() is called on the parent of the first)

OUTPUT:

If we draw the two perfect matchings simultaneously as edges of a graph, the graph obtained is a union of cycles of even lengths. The function returns an iterator for these cycles (each cycle is given as a list).

EXAMPLES:

sage: o = PerfectMatching([(1, 7), (2, 4), (3, 8), (5, 6)])
sage: p = PerfectMatching([(1, 6), (2, 7), (3, 4), (5, 8)])
sage: it = o.loops_iterator(p)
sage: next(it)
[1, 7, 2, 4, 3, 8, 5, 6]
sage: next(it)
Traceback (most recent call last):
...
StopIteration

number_of_loops(other=None)

Return the number of loops of self.

INPUT:

• other – a perfect matching of the same set of self. (if the second argument is empty, the method an_element() is called on the parent of the first)

OUTPUT:

If we draw the two perfect matchings simultaneously as edges of a graph, the graph obtained is a union of cycles of even lengths. The function returns their numbers.

EXAMPLES:

sage: m = PerfectMatching([('a','e'),('b','c'),('d','f')])
sage: n = PerfectMatching([('a','b'),('d','f'),('e','c')])
sage: m.number_of_loops(n)
2

partner(x)

Return the element in the same pair than x in the matching self.

EXAMPLES:

sage: m = PerfectMatching([(-3, 1), (2, 4), (-2, 7)])
sage: m.partner(4)
2
sage: n = PerfectMatching([('c','b'),('d','f'),('e','a')])
sage: n.partner('c')
'b'

standardization()

Return the standardization of self.

See SetPartition.standardization() for details.

EXAMPLES:

sage: n = PerfectMatching([('c','b'),('d','f'),('e','a')])
sage: n.standardization()
[(1, 5), (2, 3), (4, 6)]

to_graph()

Return the graph corresponding to the perfect matching.

OUTPUT:

The realization of self as a graph.

EXAMPLES:

sage: PerfectMatching([[1,3], [4,2]]).to_graph().edges(sort=True, labels=False)
[(1, 3), (2, 4)]
sage: PerfectMatching([[1,4], [3,2]]).to_graph().edges(sort=True, labels=False)
[(1, 4), (2, 3)]
sage: PerfectMatching([]).to_graph().edges(sort=True, labels=False)
[]

to_noncrossing_set_partition()

Return the noncrossing set partition (on half as many elements) corresponding to the perfect matching if the perfect matching is noncrossing, and otherwise gives an error.

OUTPUT:

The realization of self as a noncrossing set partition.

EXAMPLES:

sage: PerfectMatching([[1,3], [4,2]]).to_noncrossing_set_partition()
Traceback (most recent call last):
...
ValueError: matching must be non-crossing
sage: PerfectMatching([[1,4], [3,2]]).to_noncrossing_set_partition()
{{1, 2}}
sage: PerfectMatching([]).to_noncrossing_set_partition()
{}

class sage.combinat.perfect_matching.PerfectMatchings(s)

Bases: sage.combinat.set_partition.SetPartitions_set

Perfect matchings of a ground set.

INPUT:

• s – an iterable of hashable objects or an integer

EXAMPLES:

If the argument s is an integer \(n\), it will be transformed into the set \(\{1, \ldots, n\}\):

sage: M = PerfectMatchings(6); M
Perfect matchings of {1, 2, 3, 4, 5, 6}
sage: PerfectMatchings([-1, -3, 1, 2])
Perfect matchings of {1, 2, -3, -1}

One can ask for the list, the cardinality or an element of a set of perfect matching:

sage: PerfectMatchings(4).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]
sage: PerfectMatchings(8).cardinality()
105
sage: M = PerfectMatchings(('a', 'e', 'b', 'f', 'c', 'd'))
sage: x = M.an_element()
sage: x # random
[('a', 'c'), ('b', 'e'), ('d', 'f')]
sage: all(PerfectMatchings(i).an_element() in PerfectMatchings(i)
....:     for i in range(2,11,2))
True

Element

alias of PerfectMatching

Weingarten_matrix(N)

Return the Weingarten matrix corresponding to the set of PerfectMatchings self.

It is a useful theoretical tool to compute polynomial integrals over the orthogonal group \(O_N\) (see [CM]).

EXAMPLES:

sage: M = PerfectMatchings(4).Weingarten_matrix(var('N'))
sage: N*(N-1)*(N+2)*M.apply_map(factor)
[N + 1    -1    -1]
[   -1 N + 1    -1]
[   -1    -1 N + 1]

base_set()

Return the base set of self.

EXAMPLES:

sage: PerfectMatchings(3).base_set()
{1, 2, 3}

base_set_cardinality()

Return the cardinality of the base set of self.

EXAMPLES:

sage: PerfectMatchings(3).base_set_cardinality()
3

cardinality()

Return the cardinality of the set of perfect matchings self.

This is \(1*3*5*...*(2n-1)\), where \(2n\) is the size of the ground set.

EXAMPLES:

sage: PerfectMatchings(8).cardinality()
105
sage: PerfectMatchings([1,2,3,4]).cardinality()
3
sage: PerfectMatchings(3).cardinality()
0
sage: PerfectMatchings([]).cardinality()
1

random_element()

Return a random element of self.

EXAMPLES:

sage: M = PerfectMatchings(('a', 'e', 'b', 'f', 'c', 'd'))
sage: x = M.random_element()
sage: x # random
[('a', 'b'), ('c', 'd'), ('e', 'f')]