Infinite gammoids: minors and duality

Authors Seyed Hadi Afzali Borujeni, Hiu Fai Law, Malte Müller

Publication date 25 January 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2277, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

contractions gammoids infinite matroids linkages matchings transversal matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)

Abstract: This sequel to our paper (Infinite gammoids, 2014) considers minors and duals of infinite gammoids. We prove that a class of gammoids definable 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 introduced by Carmesin (Topological infinite gammoids, and a new Menger-type theorem for infinite graphs, 2014) 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 alternating-comb-free strict gammoids, introduced in the prequel, 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.

Review text

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Infinite gammoids: minors and duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q907227)