Infinite strict gammoids

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. An independent set is maximal precisely if it admits a linkage onto the sinks. In the infinit...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-10
Main Authors: Afzali, Hadi, Law, Hiu-Fai, Müller, Malte
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Substructures
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. An independent set is maximal precisely if it admits a linkage 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 to the characterization. We then show that the sets linkable onto the sinks form the bases of a (possibly non-finitary) matroid precisely when the substructure does not occur.
ISSN:2331-8422