Infinite Gammoids

  • Seyed Hadi Afzali Borujeni
  • Hiu-Fai Law
  • Malte Müller
Keywords: Infinite matroids, strict gammoids, transversal matroid, linkage, infinite digraphs, rays

Abstract

Finite strict gammoids, introduced in the early 1970's, are matroids defined via finite digraphs equipped with some set of sinks: a set of vertices is independent if it admits a linkage to these sinks. In particular, an independent set is maximal (i.e. a base) precisely if it is linkable onto the sinks.

In the infinite setting, this characterization of the maximal independent sets need not hold. We identify a type of substructure as the unique obstruction. This allows us to prove that the sets linkable onto the sinks form the bases of a (possibly non-finitary) matroid if and only if this substructure does not occur.

Published
2015-03-06
Article Number
P1.53