Finitary and cofinitary gammoids

• Published in: Discrete Applied Mathematics 2016-08, Vol.209, p.2-10
• Main Authors: Afzali Borujeni, Seyed Hadi, Law, Hiu-Fai, Müller, Malte
• Format: Article
• Language: English
• Subjects: Circuits; Finitary; Gammoid; Graph theory; Graphs; Grounds; Infinite matroid; Mathematical analysis; Sums; Transversal matroid; Vertex sets
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2015.07.030

A gammoid is a matroid defined using linkability of vertex sets in a (possibly infinite) digraph. Related types of matroids are strict gammoids and transversal matroids, three aspects of which will be considered as follows. First, we investigate the interaction between matroid properties of strict gammoids and transversal matroids and graphic properties of the defining graphs. In particular, we characterize cofinitary strict gammoids and cofinitary transversal matroids among, respectively, strict gammoids and transversal matroids in terms of the defining graphs. The set of finite circuits of a matroid defines the finitarization matroid on the same ground set. A matroid is nearly finitary if every base can be extended to a base of the finitarization matroid by adding finitely many elements. Aigner-Horev et al. (2011)  [6] raised the question whether the number of such additions is bounded for a fixed nearly finitary matroid. We answer this question positively in the classes of strict gammoids and transversal matroids. Piff and Welsh (1970) proved the classical result that a finite strict gammoid/transversal matroid is representable over any large enough field. In this direction, we prove that finitary strict gammoids and transversal matroids are representable over some field, and hence the cofinitary counterparts are thin sums representable, a new notion of representability introduced by Bruhn and Diestel (2011).