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 hyperoctahedral groups (see [MV], Chapter VII of [Mac1995] and [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')]

>>> from sage.all import *
>>> 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
[Python] 
>>> from sage.all import *
>>> n = PerfectMatching([Integer(3),Integer(8),Integer(1),Integer(7),Integer(6),Integer(5),Integer(4),Integer(2)]); n
[(1, 3), (2, 8), (4, 7), (5, 6)]
>>> 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)]]

>>> from sage.all import *
>>> PerfectMatchings(Integer(4)).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]
class sage.combinat.perfect_matching.PerfectMatching(parent, s, check=True, sort=True)[source]

Bases: 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

>>> from sage.all import *
>>> m = PerfectMatching([('a','e'),('b','c'),('d','f')]);m
[('a', 'e'), ('b', 'c'), ('d', 'f')]
>>> n = PerfectMatching([Integer(3),Integer(8),Integer(1),Integer(7),Integer(6),Integer(5),Integer(4),Integer(2)]);n
[(1, 3), (2, 8), (4, 7), (5, 6)]
>>> 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}
[Python] 
>>> from sage.all import *
>>> 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

>>> from sage.all import *
>>> PerfectMatching([(Integer(1), Integer(4)), (Integer(2), Integer(3)), (Integer(5), Integer(6))]).is_noncrossing()
True
Weingarten_function(d, other=None)[source]

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')                                                              # needs sage.symbolic
N
sage: m = PerfectMatching([(1,3),(2,4)])
sage: n = PerfectMatching([(1,2),(3,4)])
sage: factor(m.Weingarten_function(N, n))                                   # needs sage.symbolic
-1/((N + 2)*(N - 1)*N)

>>> from sage.all import *
>>> var('N')                                                              # needs sage.symbolic
N
>>> m = PerfectMatching([(Integer(1),Integer(3)),(Integer(2),Integer(4))])
>>> n = PerfectMatching([(Integer(1),Integer(2)),(Integer(3),Integer(4))])
>>> factor(m.Weingarten_function(N, n))                                   # needs sage.symbolic
-1/((N + 2)*(N - 1)*N)
loop_type(other=None)[source]

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]

>>> from sage.all import *
>>> m = PerfectMatching([('a','e'),('b','c'),('d','f')])
>>> n = PerfectMatching([('a','b'),('d','f'),('e','c')])
>>> m.loop_type(n)
[2, 1]
loops(other=None)[source]

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]]

>>> from sage.all import *
>>> m = PerfectMatching([('a','e'),('b','c'),('d','f')])
>>> n = PerfectMatching([('a','b'),('d','f'),('e','c')])
>>> loops = m.loops(n)
>>> loops # random
[['a', 'e', 'c', 'b'], ['d', 'f']]

>>> o = PerfectMatching([(Integer(1), Integer(7)), (Integer(2), Integer(4)), (Integer(3), Integer(8)), (Integer(5), Integer(6))])
>>> p = PerfectMatching([(Integer(1), Integer(6)), (Integer(2), Integer(7)), (Integer(3), Integer(4)), (Integer(5), Integer(8))])
>>> o.loops(p)
[[1, 7, 2, 4, 3, 8, 5, 6]]
loops_iterator(other=None)[source]

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

>>> from sage.all import *
>>> o = PerfectMatching([(Integer(1), Integer(7)), (Integer(2), Integer(4)), (Integer(3), Integer(8)), (Integer(5), Integer(6))])
>>> p = PerfectMatching([(Integer(1), Integer(6)), (Integer(2), Integer(7)), (Integer(3), Integer(4)), (Integer(5), Integer(8))])
>>> it = o.loops_iterator(p)
>>> next(it)
[1, 7, 2, 4, 3, 8, 5, 6]
>>> next(it)
Traceback (most recent call last):
...
StopIteration
number_of_loops(other=None)[source]

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

>>> from sage.all import *
>>> m = PerfectMatching([('a','e'),('b','c'),('d','f')])
>>> n = PerfectMatching([('a','b'),('d','f'),('e','c')])
>>> m.number_of_loops(n)
2
partner(x)[source]

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'

>>> from sage.all import *
>>> m = PerfectMatching([(-Integer(3), Integer(1)), (Integer(2), Integer(4)), (-Integer(2), Integer(7))])
>>> m.partner(Integer(4))
2
>>> n = PerfectMatching([('c','b'),('d','f'),('e','a')])
>>> n.partner('c')
'b'
standardization()[source]

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)]

>>> from sage.all import *
>>> n = PerfectMatching([('c','b'),('d','f'),('e','a')])
>>> n.standardization()
[(1, 5), (2, 3), (4, 6)]
to_graph()[source]

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,           # needs sage.graphs
....:                                                  labels=False)
[(1, 3), (2, 4)]
sage: PerfectMatching([[1,4], [3,2]]).to_graph().edges(sort=True,           # needs sage.graphs
....:                                                  labels=False)
[(1, 4), (2, 3)]
sage: PerfectMatching([]).to_graph().edges(sort=True, labels=False)         # needs sage.graphs
[]

>>> from sage.all import *
>>> PerfectMatching([[Integer(1),Integer(3)], [Integer(4),Integer(2)]]).to_graph().edges(sort=True,           # needs sage.graphs
...                                                  labels=False)
[(1, 3), (2, 4)]
>>> PerfectMatching([[Integer(1),Integer(4)], [Integer(3),Integer(2)]]).to_graph().edges(sort=True,           # needs sage.graphs
...                                                  labels=False)
[(1, 4), (2, 3)]
>>> PerfectMatching([]).to_graph().edges(sort=True, labels=False)         # needs sage.graphs
[]
to_noncrossing_set_partition()[source]

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()
{}

>>> from sage.all import *
>>> PerfectMatching([[Integer(1),Integer(3)], [Integer(4),Integer(2)]]).to_noncrossing_set_partition()
Traceback (most recent call last):
...
ValueError: matching must be non-crossing
>>> PerfectMatching([[Integer(1),Integer(4)], [Integer(3),Integer(2)]]).to_noncrossing_set_partition()
{{1, 2}}
>>> PerfectMatching([]).to_noncrossing_set_partition()
{}
class sage.combinat.perfect_matching.PerfectMatchings(s)[source]

Bases: 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}

>>> from sage.all import *
>>> M = PerfectMatchings(Integer(6)); M
Perfect matchings of {1, 2, 3, 4, 5, 6}
>>> PerfectMatchings([-Integer(1), -Integer(3), Integer(1), Integer(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
[Python] 
>>> from sage.all import *
>>> PerfectMatchings(Integer(4)).list()
[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]
>>> PerfectMatchings(Integer(8)).cardinality()
105
>>> M = PerfectMatchings(('a', 'e', 'b', 'f', 'c', 'd'))
>>> x = M.an_element()
>>> x # random
[('a', 'c'), ('b', 'e'), ('d', 'f')]
>>> all(PerfectMatchings(i).an_element() in PerfectMatchings(i)
...     for i in range(Integer(2),Integer(11),Integer(2)))
True
Element[source]

alias of PerfectMatching

Weingarten_matrix(N)[source]

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'))                   # needs sage.symbolic
sage: N*(N-1)*(N+2)*M.apply_map(factor)                                     # needs sage.symbolic
[N + 1    -1    -1]
[   -1 N + 1    -1]
[   -1    -1 N + 1]

>>> from sage.all import *
>>> M = PerfectMatchings(Integer(4)).Weingarten_matrix(var('N'))                   # needs sage.symbolic
>>> N*(N-Integer(1))*(N+Integer(2))*M.apply_map(factor)                                     # needs sage.symbolic
[N + 1    -1    -1]
[   -1 N + 1    -1]
[   -1    -1 N + 1]
base_set()[source]

Return the base set of self.

EXAMPLES:

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

>>> from sage.all import *
>>> PerfectMatchings(Integer(3)).base_set()
{1, 2, 3}
base_set_cardinality()[source]

Return the cardinality of the base set of self.

EXAMPLES:

sage: PerfectMatchings(3).base_set_cardinality()
3

>>> from sage.all import *
>>> PerfectMatchings(Integer(3)).base_set_cardinality()
3
cardinality()[source]

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

>>> from sage.all import *
>>> PerfectMatchings(Integer(8)).cardinality()
105
>>> PerfectMatchings([Integer(1),Integer(2),Integer(3),Integer(4)]).cardinality()
3
>>> PerfectMatchings(Integer(3)).cardinality()
0
>>> PerfectMatchings([]).cardinality()
1
random_element()[source]

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')]

>>> from sage.all import *
>>> M = PerfectMatchings(('a', 'e', 'b', 'f', 'c', 'd'))
>>> x = M.random_element()
>>> x # random
[('a', 'b'), ('c', 'd'), ('e', 'f')]