Infinite gammoids: minors and duality (Q907227)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Infinite gammoids: minors and duality |
scientific article |
Statements
Infinite gammoids: minors and duality (English)
0 references
25 January 2016
0 references
Summary: This sequel to \textit{S. H. Afzali Borujeni} et. al. [``Finitary and cofinitary gammoids'', Discrete Appl. Math. (to appear), \url{doi:10.1016/j.dam.2015.07.030}] considers minors and duals of infinite gammoids. We prove that the class of gammoids defined by digraphs not containing a certain type of substructure, called an outgoing comb, is minor-closed. Also, we prove that finite-rank minors of gammoids are gammoids. Furthermore, the topological gammoids of \textit{J. Carmesin} [``Topological infinite gammoids, and a new Menger-type theorem for infinite graphs'', Preprint, \url{arXiv:1404.0151}] are proved to coincide, as matroids, with the finitary gammoids. A corollary is that topological gammoids are minor-closed. It is a well-known fact that the dual of any finite strict gammoid is a transversal matroid. The class of strict gammoids defined by digraphs not containing alternating combs, introduced in Afzali Borujeni et. al. [loc. cit.], contains examples which are not dual to any transversal matroid. However, we describe the duals of matroids in this class as a natural extension of transversal matroids. While finite gammoids are closed under duality, we construct a strict gammoid that is not dual to any gammoid.
0 references
infinite matroids
0 references
gammoids
0 references
transversal matroids
0 references
matchings
0 references
linkages
0 references
contractions
0 references
0 references