کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418451 681673 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finitary and cofinitary gammoids
ترجمه فارسی عنوان
برهان متناهی مبنا و گامویدهای برهان متناهی مبنا مشترک
کلمات کلیدی
ماتروید بی نهایت؛ گاموید؛ ماتروید متقاطع ؛ برهان متناهی مبنا
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 2–10
نویسندگان
, , ,