Transversal matroids

A transversal matroid arises from a groundset \(E\) and a collection \(A\) of sets over the groundset. This can be modeled as a bipartite graph \(B\), where the vertices on the left are groundset elements, the vertices on the right are the sets, and edges represent containment. Then a set \(X\) from the groundset is independent if and only if \(X\) has a matching in \(B\).

To construct a transversal matroid, first import TransversalMatroid from sage.matroids.transversal_matroid. The input should be a set system, formatted as an iterable of iterables:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[3, 4, 5, 6, 7, 8]] * 3
sage: M = TransversalMatroid(sets); M
Transversal matroid of rank 3 on 6 elements, with 3 sets
sage: M.groundset()
frozenset({3, 4, 5, 6, 7, 8})
sage: M.is_isomorphic(matroids.Uniform(3, 6))
True
sage: M = TransversalMatroid([[0, 1], [1, 2, 3], [3, 4, 5]],
....:                        set_labels=['1', '2', '3'])
sage: M.graph().vertices()
['1', '2', '3', 0, 1, 2, 3, 4, 5]

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(3), Integer(4), Integer(5), Integer(6), Integer(7), Integer(8)]] * Integer(3)
>>> M = TransversalMatroid(sets); M
Transversal matroid of rank 3 on 6 elements, with 3 sets
>>> M.groundset()
frozenset({3, 4, 5, 6, 7, 8})
>>> M.is_isomorphic(matroids.Uniform(Integer(3), Integer(6)))
True
>>> M = TransversalMatroid([[Integer(0), Integer(1)], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(5)]],
...                        set_labels=['1', '2', '3'])
>>> M.graph().vertices()
['1', '2', '3', 0, 1, 2, 3, 4, 5]

AUTHORS:

  • Zachary Gershkoff (2017-08-07): initial version

REFERENCES:

class sage.matroids.transversal_matroid.TransversalMatroid[source]

Bases: BasisExchangeMatroid

The Transversal Matroid class.

INPUT:

  • sets – iterable of iterables of elements

  • groundset – (optional) iterable containing names of groundset elements

  • set_labels – (optional) list of labels in 1-1 correspondence with the iterables in sets

  • matching – (optional) dictionary specifying a maximal matching between elements and set labels

OUTPUT:

An instance of TransversalMatroid. The sets specified in sets define the matroid. If matching is not specified, the constructor will determine a matching to use for basis exchange.

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1, 2, 3]] * 3
sage: M = TransversalMatroid(sets)
sage: M.full_rank()
3
sage: M.bases_count()
4
sage: sum(1 for b in M.bases())
4

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)]] * Integer(3)
>>> M = TransversalMatroid(sets)
>>> M.full_rank()
3
>>> M.bases_count()
4
>>> sum(Integer(1) for b in M.bases())
4


sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: M = TransversalMatroid(sets=[['a', 'c']], groundset=['a', 'c', 'd'])
sage: M.loops()
frozenset({'d'})
sage: M.full_rank()
1

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> M = TransversalMatroid(sets=[['a', 'c']], groundset=['a', 'c', 'd'])
>>> M.loops()
frozenset({'d'})
>>> M.full_rank()
1
graph()[source]

Return a bipartite graph representing the transversal matroid.

A transversal matroid can be represented as a set system, or as a bipartite graph with one color class corresponding to the groundset and the other to the sets of the set system. This method returns that bipartite graph.

OUTPUT: Graph

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: edgedict = {5: [0, 1, 2, 3], 6: [1, 2], 7: [1, 3, 4]}
sage: B = BipartiteGraph(edgedict)
sage: M = TransversalMatroid(edgedict.values(), set_labels=edgedict.keys())
sage: M.graph() == B
True
sage: M2 = TransversalMatroid(edgedict.values())
sage: B2 = M2.graph()
sage: B2 == B
False
sage: B2.is_isomorphic(B)
True

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> edgedict = {Integer(5): [Integer(0), Integer(1), Integer(2), Integer(3)], Integer(6): [Integer(1), Integer(2)], Integer(7): [Integer(1), Integer(3), Integer(4)]}
>>> B = BipartiteGraph(edgedict)
>>> M = TransversalMatroid(edgedict.values(), set_labels=edgedict.keys())
>>> M.graph() == B
True
>>> M2 = TransversalMatroid(edgedict.values())
>>> B2 = M2.graph()
>>> B2 == B
False
>>> B2.is_isomorphic(B)
True
is_valid(certificate=False)[source]

Test whether the matching in memory is a valid maximal matching.

The data for a transversal matroid is a set system, which is always valid, but it is possible for a user to provide invalid input with the matching parameter. This checks that the matching provided is indeed a matching, fits in the set system, and is maximal.

EXAMPLES:

sage: from sage.matroids.transversal_matroid import *
sage: sets = [[0, 1, 2, 3], [1, 2], [1, 3, 4]]
sage: set_labels = [5, 6, 7]
sage: M = TransversalMatroid(sets, set_labels=set_labels)
sage: M.is_valid()
True
sage: m = {0: 5, 1: 5, 3: 7}  # not a matching
sage: TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False
sage: m = {2: 6, 3: 7}  # not maximal
sage: TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False
sage: m = {0: 6, 1: 5, 3: 7}  # not in the set system
sage: TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import *
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(1), Integer(2)], [Integer(1), Integer(3), Integer(4)]]
>>> set_labels = [Integer(5), Integer(6), Integer(7)]
>>> M = TransversalMatroid(sets, set_labels=set_labels)
>>> M.is_valid()
True
>>> m = {Integer(0): Integer(5), Integer(1): Integer(5), Integer(3): Integer(7)}  # not a matching
>>> TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False
>>> m = {Integer(2): Integer(6), Integer(3): Integer(7)}  # not maximal
>>> TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False
>>> m = {Integer(0): Integer(6), Integer(1): Integer(5), Integer(3): Integer(7)}  # not in the set system
>>> TransversalMatroid(sets, set_labels=set_labels, matching=m).is_valid()
False
reduce_presentation()[source]

Return an equal transversal matroid where the number of sets equals the rank.

Every transversal matroid \(M\) has a presentation with \(r(M)\) sets, and if \(M\) has no coloops, then every presentation has \(r(M)\) nonempty sets. This method discards extra sets if \(M\) has coloops.

OUTPUT: TransversalMatroid with a reduced presentation

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1], [2], [2]]
sage: M = TransversalMatroid(sets); M
Transversal matroid of rank 2 on 3 elements, with 3 sets
sage: N = M.reduce_presentation(); N
Transversal matroid of rank 2 on 3 elements, with 2 sets
sage: N.equals(M)
True
sage: N == M
False
sage: sets = [[0, 1], [], [], [2]]
sage: M1 = TransversalMatroid(sets); M1
Transversal matroid of rank 2 on 3 elements, with 4 sets
sage: M1.reduce_presentation()
Transversal matroid of rank 2 on 3 elements, with 2 sets

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1)], [Integer(2)], [Integer(2)]]
>>> M = TransversalMatroid(sets); M
Transversal matroid of rank 2 on 3 elements, with 3 sets
>>> N = M.reduce_presentation(); N
Transversal matroid of rank 2 on 3 elements, with 2 sets
>>> N.equals(M)
True
>>> N == M
False
>>> sets = [[Integer(0), Integer(1)], [], [], [Integer(2)]]
>>> M1 = TransversalMatroid(sets); M1
Transversal matroid of rank 2 on 3 elements, with 4 sets
>>> M1.reduce_presentation()
Transversal matroid of rank 2 on 3 elements, with 2 sets


sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1, 2, 3]] * 3
sage: M = TransversalMatroid(sets)
sage: N = M.reduce_presentation()
sage: M == N
True

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)]] * Integer(3)
>>> M = TransversalMatroid(sets)
>>> N = M.reduce_presentation()
>>> M == N
True
set_labels()[source]

Return the labels used for the transversal sets.

This method will return a list of the labels used of the non-ground set vertices of the bipartite graph used to represent the transversal matroid. This method does not set anything.

OUTPUT: list

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: M = TransversalMatroid([[0, 1], [1, 2, 3], [3, 4, 7]])
sage: M.set_labels()
['s0', 's1', 's2']
sage: M.graph().vertices()
['s0', 's1', 's2', 0, 1, 2, 3, 4, 7]

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> M = TransversalMatroid([[Integer(0), Integer(1)], [Integer(1), Integer(2), Integer(3)], [Integer(3), Integer(4), Integer(7)]])
>>> M.set_labels()
['s0', 's1', 's2']
>>> M.graph().vertices()
['s0', 's1', 's2', 0, 1, 2, 3, 4, 7]
sets()[source]

Return the sets of self.

A transversal matroid can be viewed as a groundset with a collection from its powerset. This is represented as a bipartite graph, where an edge represents containment.

OUTPUT: list of lists that correspond to the sets of the transversal matroid

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1, 2, 3], [1, 2], [3, 4]]
sage: set_labels = [5, 6, 7]
sage: M = TransversalMatroid(sets, set_labels=set_labels)
sage: sorted(M.sets()) == sorted(sets)
True

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(1), Integer(2)], [Integer(3), Integer(4)]]
>>> set_labels = [Integer(5), Integer(6), Integer(7)]
>>> M = TransversalMatroid(sets, set_labels=set_labels)
>>> sorted(M.sets()) == sorted(sets)
True
transversal_extension(element=None, newset=False, sets=None)[source]

Return a TransversalMatroid extended by an element.

This will modify the presentation of the transversal matroid by adding a new element, and placing this element in the specified sets. It is also possible to use this method to create a new set that will have the new element as its only member, making it a coloop.

INPUT:

  • element – (optional) the name for the new element

  • newset – (optional) if specified, the element will be given its own set

  • sets – iterable of labels (default: None) representing the sets in the current presentation that the new element will belong to

OUTPUT:

A TransversalMatroid with a groundset element added to specified sets. Note that the newset option will make the new element a coloop. If newset == True, a name will be generated; otherwise the value of newset will be used.

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: M = TransversalMatroid([['a', 'c']], groundset=['a', 'c'], set_labels=['b'])
sage: M1 = M.transversal_extension(element='d', newset='e')
sage: M2 = M.transversal_extension(element='d', newset=True)
sage: M1.coloops()
frozenset({'d'})
sage: True in M2.graph().vertices()
False
sage: M1.is_isomorphic(M2)
True
sage: M3 = M.transversal_extension('d', sets=['b'])
sage: M3.is_isomorphic(matroids.Uniform(1, 3))
True
sage: M4 = M.transversal_extension('d', sets=['a'])
Traceback (most recent call last):
...
ValueError: sets do not match presentation
sage: M4 = M.transversal_extension('a', sets=['b'])
Traceback (most recent call last):
...
ValueError: cannot extend by element already in groundset
sage: M2.transversal_extension(newset='b')
Traceback (most recent call last):
...
ValueError: newset is already a vertex in the presentation
sage: M5 = M1.transversal_extension()
sage: len(M5.loops())
1
sage: M2.transversal_extension(element='b')
Transversal matroid of rank 2 on 4 elements, with 2 sets

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> M = TransversalMatroid([['a', 'c']], groundset=['a', 'c'], set_labels=['b'])
>>> M1 = M.transversal_extension(element='d', newset='e')
>>> M2 = M.transversal_extension(element='d', newset=True)
>>> M1.coloops()
frozenset({'d'})
>>> True in M2.graph().vertices()
False
>>> M1.is_isomorphic(M2)
True
>>> M3 = M.transversal_extension('d', sets=['b'])
>>> M3.is_isomorphic(matroids.Uniform(Integer(1), Integer(3)))
True
>>> M4 = M.transversal_extension('d', sets=['a'])
Traceback (most recent call last):
...
ValueError: sets do not match presentation
>>> M4 = M.transversal_extension('a', sets=['b'])
Traceback (most recent call last):
...
ValueError: cannot extend by element already in groundset
>>> M2.transversal_extension(newset='b')
Traceback (most recent call last):
...
ValueError: newset is already a vertex in the presentation
>>> M5 = M1.transversal_extension()
>>> len(M5.loops())
1
>>> M2.transversal_extension(element='b')
Transversal matroid of rank 2 on 4 elements, with 2 sets


sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1, 2, 3], [1, 2], [1, 3, 4]]
sage: M = TransversalMatroid(sets, groundset=range(5), set_labels=[5, 6, 7])
sage: N = M.delete(2)
sage: M1 = N.transversal_extension(element=2, sets=[5, 6])
sage: M1 == M
True

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)], [Integer(1), Integer(2)], [Integer(1), Integer(3), Integer(4)]]
>>> M = TransversalMatroid(sets, groundset=range(Integer(5)), set_labels=[Integer(5), Integer(6), Integer(7)])
>>> N = M.delete(Integer(2))
>>> M1 = N.transversal_extension(element=Integer(2), sets=[Integer(5), Integer(6)])
>>> M1 == M
True


sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[0, 1, 2, 3]] * 3
sage: M = TransversalMatroid(sets, set_labels=[4, 5, 6])
sage: N = M.transversal_extension(element='a', newset=True, sets=[4])
sage: N.graph().degree('a')
2

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(0), Integer(1), Integer(2), Integer(3)]] * Integer(3)
>>> M = TransversalMatroid(sets, set_labels=[Integer(4), Integer(5), Integer(6)])
>>> N = M.transversal_extension(element='a', newset=True, sets=[Integer(4)])
>>> N.graph().degree('a')
2
transversal_extensions(element=None, sets=None)[source]

Return an iterator of extensions based on the transversal presentation.

This method will take an extension by adding an element to every possible sub-collection of the collection of desired sets. No checking is done for equal matroids. It is advised to make sure the presentation has as few sets as possible by using reduce_presentation()

INPUT:

  • element – (optional) the name of the new element

  • sets – (optional) list containing names of sets in the matroid’s presentation

OUTPUT: iterator over instances of TransversalMatroid

If sets is not specified, every set will be used.

EXAMPLES:

sage: from sage.matroids.transversal_matroid import TransversalMatroid
sage: sets = [[3, 4, 5, 6]] * 3
sage: M = TransversalMatroid(sets, set_labels=[0, 1, 2])
sage: len([N for N in M.transversal_extensions()])
8
sage: len([N for N in M.transversal_extensions(sets=[0, 1])])
4
sage: set(sorted([N.groundset() for N in M.transversal_extensions(element=7)]))
{frozenset({3, 4, 5, 6, 7})}

>>> from sage.all import *
>>> from sage.matroids.transversal_matroid import TransversalMatroid
>>> sets = [[Integer(3), Integer(4), Integer(5), Integer(6)]] * Integer(3)
>>> M = TransversalMatroid(sets, set_labels=[Integer(0), Integer(1), Integer(2)])
>>> len([N for N in M.transversal_extensions()])
8
>>> len([N for N in M.transversal_extensions(sets=[Integer(0), Integer(1)])])
4
>>> set(sorted([N.groundset() for N in M.transversal_extensions(element=Integer(7))]))
{frozenset({3, 4, 5, 6, 7})}