Gammoids

Let \(D\) be a directed graph and let \(E\) and \(T\) be not necessarily disjoint sets of vertices of \(D\). Say a subset \(X\) of \(E\) is in a collection \(I\) if \(X\) can be linked into a subset of \(T\). This defines a gammoid \((E, I)\), where \(E\) is the groundset of a matroid and \(I\) is its independent sets.

Some authors use a reverse convention, where instead of a set \(T\) of roots, they have a starting set \(S\) that is linked into subsets of \(E\). Here we use the convention that the vertices \(T\) are at the end of the directed paths, not the beginning.

To construct a gammoid, first import Gammoid from sage.matroids.gammoid. A digraph and a list of roots from the vertex set are required for input:

sage: from sage.matroids.gammoid import *
sage: edgelist = [(0,1),(1,2),(2,3),(3,4)]
sage: D = DiGraph(edgelist)
sage: M = Gammoid(D, roots=[4]); M
Gammoid of rank 1 on 5 elements
sage: N = Gammoid(D, roots=[4], groundset=range(1,5)); N
Gammoid of rank 1 on 4 elements
sage: M.delete(0) == N
True
sage: N.is_isomorphic(matroids.Uniform(1,4))
True
sage: O = Gammoid(D, roots=[3]); O
Gammoid of rank 1 on 5 elements
sage: O.rank([0])
1
sage: O.rank([4])
0

>>> from sage.all import *
>>> from sage.matroids.gammoid import *
>>> edgelist = [(Integer(0),Integer(1)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4))]
>>> D = DiGraph(edgelist)
>>> M = Gammoid(D, roots=[Integer(4)]); M
Gammoid of rank 1 on 5 elements
>>> N = Gammoid(D, roots=[Integer(4)], groundset=range(Integer(1),Integer(5))); N
Gammoid of rank 1 on 4 elements
>>> M.delete(Integer(0)) == N
True
>>> N.is_isomorphic(matroids.Uniform(Integer(1),Integer(4)))
True
>>> O = Gammoid(D, roots=[Integer(3)]); O
Gammoid of rank 1 on 5 elements
>>> O.rank([Integer(0)])
1
>>> O.rank([Integer(4)])
0

AUTHORS:

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

class sage.matroids.gammoid.Gammoid(D, roots, groundset=None)[source]

Bases: Matroid

The gammoid class.

INPUT:

  • D – a loopless digraph representing the gammoid

  • roots – a subset of the vertices

  • groundset – (optional) a subset of the vertices

OUTPUT: Gammoid; if groundset is not specified, the entire vertex set is used (and the gammoid will be strict)

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: D = digraphs.TransitiveTournament(5)
sage: M = Gammoid(D, roots=[3, 4]); M
Gammoid of rank 2 on 5 elements
sage: M.is_isomorphic(matroids.Uniform(2, 5))
True
sage: D.add_vertex(6)
sage: N = Gammoid(D, roots=[3, 4])
sage: N.loops()
frozenset({6})
sage: O = Gammoid(D, roots=[3, 4, 6])
sage: O.coloops()
frozenset({6})
sage: O.full_rank()
3
sage: P = Gammoid(D, roots=[3, 4], groundset=[0, 2, 3]); P
Gammoid of rank 2 on 3 elements

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> D = digraphs.TransitiveTournament(Integer(5))
>>> M = Gammoid(D, roots=[Integer(3), Integer(4)]); M
Gammoid of rank 2 on 5 elements
>>> M.is_isomorphic(matroids.Uniform(Integer(2), Integer(5)))
True
>>> D.add_vertex(Integer(6))
>>> N = Gammoid(D, roots=[Integer(3), Integer(4)])
>>> N.loops()
frozenset({6})
>>> O = Gammoid(D, roots=[Integer(3), Integer(4), Integer(6)])
>>> O.coloops()
frozenset({6})
>>> O.full_rank()
3
>>> P = Gammoid(D, roots=[Integer(3), Integer(4)], groundset=[Integer(0), Integer(2), Integer(3)]); P
Gammoid of rank 2 on 3 elements
digraph()[source]

Return the digraph associated with the gammoid.

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: edgelist = [(0, 4), (0, 5), (1, 0), (1, 4), (2, 0), (2, 1), (2, 3),
....:             (2, 6), (3, 4), (3, 5), (4, 0), (5, 2), (6, 5)]
sage: D = DiGraph(edgelist)
sage: M = Gammoid(D, roots=[4, 5, 6])
sage: M.digraph() == D
True

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> edgelist = [(Integer(0), Integer(4)), (Integer(0), Integer(5)), (Integer(1), Integer(0)), (Integer(1), Integer(4)), (Integer(2), Integer(0)), (Integer(2), Integer(1)), (Integer(2), Integer(3)),
...             (Integer(2), Integer(6)), (Integer(3), Integer(4)), (Integer(3), Integer(5)), (Integer(4), Integer(0)), (Integer(5), Integer(2)), (Integer(6), Integer(5))]
>>> D = DiGraph(edgelist)
>>> M = Gammoid(D, roots=[Integer(4), Integer(5), Integer(6)])
>>> M.digraph() == D
True
digraph_plot()[source]

Plot the graph with color-coded vertices.

Vertices that are elements but not roots will be shown as blue. Vertices that are roots but not elements are red. Vertices that are both are pink, and vertices that are neither are grey.

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: D = digraphs.TransitiveTournament(4)
sage: M = Gammoid(D, roots=[2, 3])
sage: M.digraph_plot()
Graphics object consisting of 11 graphics primitives

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> D = digraphs.TransitiveTournament(Integer(4))
>>> M = Gammoid(D, roots=[Integer(2), Integer(3)])
>>> M.digraph_plot()
Graphics object consisting of 11 graphics primitives
gammoid_extension(vertex, neighbors=[])[source]

Return a gammoid extended by an element.

The new element can be a vertex of the digraph that is not in the starting set, or it can be a new source vertex.

INPUT:

  • vertex – a vertex of the gammoid’s digraph that is not already in the groundset, or a new vertex

  • neighbors – (optional) a set of vertices of the digraph

OUTPUT:

A Gammoid. If vertex is not already in the graph, then the new vertex will be have edges to neighbors. The new vertex will have in degree \(0\) regardless of whether or not neighbors is specified.

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: edgedict = {1: [2], 2: [3], 4: [1, 5], 5: [2, 3, 8],
....:             6: [4, 7], 7: [5, 8]}
sage: D = DiGraph(edgedict)
sage: M = Gammoid(D, roots=[2, 3, 4], groundset=range(2, 9))
sage: M1 = M.gammoid_extension(1)
sage: M1.groundset()
frozenset({1, 2, 3, 4, 5, 6, 7, 8})
sage: N = Gammoid(D, roots=[2, 3, 4])
sage: M1 == N
True
sage: M1.delete(1)
Gammoid of rank 3 on 7 elements
sage: M == M1.delete(1)
True
sage: M2 = M.gammoid_extension(9); sorted(M2.loops())
[8, 9]
sage: M4 = M.gammoid_extension(9, [1, 2, 3])
sage: M4.digraph().neighbors_out(9)
[1, 2, 3]
sage: M4.digraph().neighbors_in(9)
[]

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> edgedict = {Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(4): [Integer(1), Integer(5)], Integer(5): [Integer(2), Integer(3), Integer(8)],
...             Integer(6): [Integer(4), Integer(7)], Integer(7): [Integer(5), Integer(8)]}
>>> D = DiGraph(edgedict)
>>> M = Gammoid(D, roots=[Integer(2), Integer(3), Integer(4)], groundset=range(Integer(2), Integer(9)))
>>> M1 = M.gammoid_extension(Integer(1))
>>> M1.groundset()
frozenset({1, 2, 3, 4, 5, 6, 7, 8})
>>> N = Gammoid(D, roots=[Integer(2), Integer(3), Integer(4)])
>>> M1 == N
True
>>> M1.delete(Integer(1))
Gammoid of rank 3 on 7 elements
>>> M == M1.delete(Integer(1))
True
>>> M2 = M.gammoid_extension(Integer(9)); sorted(M2.loops())
[8, 9]
>>> M4 = M.gammoid_extension(Integer(9), [Integer(1), Integer(2), Integer(3)])
>>> M4.digraph().neighbors_out(Integer(9))
[1, 2, 3]
>>> M4.digraph().neighbors_in(Integer(9))
[]
gammoid_extensions(vertices=None)[source]

Return an iterator of Gammoid extensions.

This will only consider extensions from vertices that are already present in the digraph.

INPUT:

  • vertices – (optional) a list of vertices not in the digraph

OUTPUT:

An iterator of Gammoids. If vertices is not specified, every vertex not already in the groundset will be considered.

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: M = Gammoid(digraphs.TransitiveTournament(5), roots=[3, 4],
....:             groundset=[0, 1, 4])
sage: [sorted(M1.groundset()) for M1 in M.gammoid_extensions()]
[[0, 1, 2, 4], [0, 1, 3, 4]]
sage: N = Gammoid(digraphs.TransitiveTournament(5), roots=[3, 4])
sage: [sorted(N1.groundset()) for N1 in N.gammoid_extensions()]
[]

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> M = Gammoid(digraphs.TransitiveTournament(Integer(5)), roots=[Integer(3), Integer(4)],
...             groundset=[Integer(0), Integer(1), Integer(4)])
>>> [sorted(M1.groundset()) for M1 in M.gammoid_extensions()]
[[0, 1, 2, 4], [0, 1, 3, 4]]
>>> N = Gammoid(digraphs.TransitiveTournament(Integer(5)), roots=[Integer(3), Integer(4)])
>>> [sorted(N1.groundset()) for N1 in N.gammoid_extensions()]
[]


sage: from sage.matroids.gammoid import Gammoid
sage: edgelist =[(i, i+1) for i in range(10)]
sage: M = Gammoid(DiGraph(edgelist), roots=[9], groundset=[0])
sage: sum(1 for M1 in M.gammoid_extensions(vertices=[3, 4, 5]))
3
sage: sum(1 for M1 in M.gammoid_extensions())
9
sage: set([M1.is_isomorphic(matroids.Uniform(1, 2))
....:      for M1 in M.gammoid_extensions()])
{True}
sage: len([M1 for M1 in M.gammoid_extensions([0, 1, 2])])
Traceback (most recent call last):
...
ValueError: vertices must be in the digraph and not already in the groundset

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> edgelist =[(i, i+Integer(1)) for i in range(Integer(10))]
>>> M = Gammoid(DiGraph(edgelist), roots=[Integer(9)], groundset=[Integer(0)])
>>> sum(Integer(1) for M1 in M.gammoid_extensions(vertices=[Integer(3), Integer(4), Integer(5)]))
3
>>> sum(Integer(1) for M1 in M.gammoid_extensions())
9
>>> set([M1.is_isomorphic(matroids.Uniform(Integer(1), Integer(2)))
...      for M1 in M.gammoid_extensions()])
{True}
>>> len([M1 for M1 in M.gammoid_extensions([Integer(0), Integer(1), Integer(2)])])
Traceback (most recent call last):
...
ValueError: vertices must be in the digraph and not already in the groundset
groundset()[source]

Return the groundset of the matroid.

EXAMPLES:

sage: from sage.matroids.gammoid import Gammoid
sage: edgelist = [(0, 4), (0, 5), (1, 0), (1, 4), (2, 0), (2, 1), (2, 3),
....:             (2, 6), (3, 4), (3, 5), (4, 0), (5, 2), (6, 5)]
sage: D = DiGraph(edgelist)
sage: M = Gammoid(D, roots=[4, 5, 6])
sage: sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]

>>> from sage.all import *
>>> from sage.matroids.gammoid import Gammoid
>>> edgelist = [(Integer(0), Integer(4)), (Integer(0), Integer(5)), (Integer(1), Integer(0)), (Integer(1), Integer(4)), (Integer(2), Integer(0)), (Integer(2), Integer(1)), (Integer(2), Integer(3)),
...             (Integer(2), Integer(6)), (Integer(3), Integer(4)), (Integer(3), Integer(5)), (Integer(4), Integer(0)), (Integer(5), Integer(2)), (Integer(6), Integer(5))]
>>> D = DiGraph(edgelist)
>>> M = Gammoid(D, roots=[Integer(4), Integer(5), Integer(6)])
>>> sorted(M.groundset())
[0, 1, 2, 3, 4, 5, 6]