Infinite Gammoids: Minors and Duality

  • Seyed Hadi Afzali Borujeni
  • Hiu-Fai Law
  • Malte Müller
Keywords: Infinite matroids, Gammoids, Transversal matroids, Matchings, Linkages, Contractions

Abstract

This sequel to Afzali Borujeni et. al. (2015) 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 Carmesin (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 strict gammoids defined by digraphs not containing alternating combs, introduced in Afzali Borujeni et. al. (2015), 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.

 

Published
2015-12-11
Article Number
P4.37