Infinite Gammoids: Minors and Duality

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

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.

 


Keywords


Infinite matroids; Gammoids; Transversal matroids; Matchings; Linkages; Contractions

Full Text:

PDF