Gammoid

Last updated

In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

Contents

The concept of a gammoid was introduced and shown to be a matroid by HazelPerfect  ( 1968 ), based on considerations related to Menger's theorem characterizing the obstacles to the existence of systems of disjoint paths. [1] Gammoids were given their name by Pym (1969) [2] and studied in more detail by Mason (1972). [3]

Definition

Let be a directed graph, be a set of starting vertices, and be a set of destination vertices (not necessarily disjoint from ). The gammoid derived from this data has as its set of elements. A subset of is independent in if there exists a set of vertex-disjoint paths whose starting points all belong to and whose ending points are exactly . [4]

A strict gammoid is a gammoid in which the set of destination vertices consists of every vertex in . Thus, a gammoid is a restriction of a strict gammoid, to a subset of its elements. [4] [5]

Example

Consider the uniform matroid on a set of elements, in which every set of or fewer elements is independent. One way to represent this matroid as a gammoid would be to form a complete bipartite graph with a set of vertices on one side of the bipartition, with a set of vertices on the other side of the bipartition, and with every edge directed from to In this graph, a subset of is the set of endpoints of a set of disjoint paths if and only if it has or fewer vertices, for otherwise there aren't enough vertices in to start the paths. The special structure of this graph shows that the uniform matroid is a transversal matroid as well as being a gammoid. [6]

Alternatively, the same uniform matroid may be represented as a gammoid on a smaller graph, with only vertices, by choosing a subset of vertices and connecting each of the chosen vertices to every other vertex in the graph. Again, a subset of the vertices of the graph can be endpoints of disjoint paths if and only if it has or fewer vertices, because otherwise there are not enough vertices that can be starts of paths. In this graph, every vertex corresponds to an element of the matroid, showing that the uniform matroid is a strict gammoid. [7]

Menger's theorem and gammoid rank

The rank of a set in a gammoid defined from a graph and vertex subsets and is, by definition, the maximum number of vertex-disjoint paths from to . By Menger's theorem, it also equals the minimum cardinality of a set that intersects every path from to . [4]

Relation to transversal matroids

A transversal matroid is defined from a family of sets: its elements are the elements of the sets, and a set of these elements is independent whenever there exists a one-to-one matching of the elements of to disjoint sets containing them, called a system of distinct representatives. Equivalently, a transversal matroid may be represented by a special kind of gammoid, defined from a directed bipartite graph that has a vertex in for each set, a vertex in for each element, and an edge from each set to each element contained in it.

Less trivially, the strict gammoids are exactly the dual matroids of the transversal matroids. To see that every strict gammoid is dual to a transversal matroid, let be a strict gammoid defined from a directed graph and starting vertex set , and consider the transversal matroid for the family of sets for each vertex , where vertex belongs to if it equals or it has an edge to . Any basis of the strict gammoid, consisting of the endpoints of some set of disjoint paths from , is the complement of a basis of the transversal matroid, matching each to the vertex such that is a path edge (or itself, if does not participate in one of the paths). Conversely every basis of the transversal matroid, consisting of a representative for each , gives rise to a complementary basis of the strict gammoid, consisting of the endpoints of the paths formed by the set of edges . This result is due to Ingleton and Piff. [4] [8]

To see, conversely, that every transversal matroid is dual to a strict gammoid, find a subfamily of the sets defining the matroid such that the subfamily has a system of distinct representatives and defines the same matroid. Form a graph that has the union of the sets as its vertices and that has an edge to the representative element of each set from the other members of the same set. Then the sets formed as above for each representative element are exactly the sets defining the original transversal matroid, so the strict gammoid formed by this graph and by the set of representative elements is dual to the given transversal matroid. [4] [8]

As an easy consequence of the Ingleton-Piff Theorem, every gammoid is a contraction of a transversal matroid. The gammoids are the smallest class of matroids that includes the transversal matroids and is closed under duality and taking minors. [4] [9] [10]

Representability

It is not true that every gammoid is regular, i.e., representable over every field. In particular, the uniform matroid is not a binary matroid, and more generally the -point line can only be represented over fields with or more elements. However, every gammoid may be represented over almost every finite field. [3] [4] More specifically, a gammoid with element set may be represented over every field that has at least elements. [4] [11] [12]

Related Research Articles

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal:

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

<span class="mw-page-title-main">Edge contraction</span> Deleting a graph edge and merging its nodes

In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex identification is a less restrictive form of this operation.

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

<span class="mw-page-title-main">Pseudoforest</span> Graph with at most one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

In the mathematical subject of matroid theory, the bicircular matroid of a graph G is the matroid B(G) whose points are the edges of G and whose independent sets are the edge sets of pseudoforests of G, that is, the edge sets in which each connected component contains at most one cycle.

In matroid theory, the dual of a matroid is another matroid that has the same elements as , and in which a set is independent if and only if has a basis set disjoint from it.

In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most r elements, for some fixed integer r. An alternative definition is that every permutation of the elements is a symmetry.

In the mathematics of infinite graphs, an end of a graph represents, intuitively, a direction in which the graph extends to infinity. Ends may be formalized mathematically as equivalence classes of infinite paths, as havens describing strategies for pursuit–evasion games on the graph, or as topological ends of topological spaces associated with the graph.

In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a capacity constraint - a maximum number of allowed elements from this category. The independent sets of a partition matroid are exactly the sets in which, for each category, the number of elements from this category is at most the category capacity.

<span class="mw-page-title-main">Matroid parity problem</span> Largest independent set of paired elements

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

References

  1. Perfect, Hazel (1968), "Applications of Menger's graph theorem", Journal of Mathematical Analysis and Applications, 22: 96–111, doi: 10.1016/0022-247X(68)90163-7 , MR   0224494 .
  2. Pym, J. S. (1969), "The Linking of Sets in Graphs", Journal of the London Mathematical Society, s1-44 (1): 542–550, doi:10.1112/jlms/s1-44.1.542 .
  3. 1 2 Mason, J. H. (1972), "On a class of matroids arising from paths in graphs", Proceedings of the London Mathematical Society, Third Series, 25 (1): 55–74, doi:10.1112/plms/s3-25.1.55, MR   0311496 .
  4. 1 2 3 4 5 6 7 8 Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets, Algorithms and Combinatorics, vol. 24, Berlin: Springer-Verlag, pp. 659–661, ISBN   3-540-44389-4, MR   1956925 .
  5. Oxley 2006 , p. 100
  6. Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pp. 48–49, ISBN   9780199202508 .
  7. Oxley (2006), p. 100.
  8. 1 2 Ingleton, A. W.; Piff, M. J. (1973), "Gammoids and transversal matroids", Journal of Combinatorial Theory, Series B, 15: 51–68, doi: 10.1016/0095-8956(73)90031-2 , MR   0329936 .
  9. Oxley 2006 , p. 115
  10. Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, pp. 222–223, ISBN   9780486474397 .
  11. Atkin, A. O. L. (1972), "Remark on a paper of Piff and Welsh", Journal of Combinatorial Theory , Series B, 13 (2): 179–182, doi: 10.1016/0095-8956(72)90053-6 , MR   0316281 .
  12. Lindström, Bernt (1973), "On the vector representations of induced matroids", The Bulletin of the London Mathematical Society, 5: 85–90, doi:10.1112/blms/5.1.85, MR   0335313 .