کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654898 1632840 2007 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Defining matroids through sequential selection
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Defining matroids through sequential selection
چکیده انگلیسی

Let EE be a finite set and SS be a collection of subsets of EE. For each x∈Ex∈E let Sx={S∈S∣x∈S}Sx={S∈S∣x∈S}. Suppose we choose elements x1,…,xnx1,…,xn in such a way that we first choose x1x1 belonging to some set of Sx1Sx1. For i=2,…,ni=2,…,n we choose xixi belonging to some set of Sxi∖(Sx1∪⋯∪Sxi−1)Sxi∖(Sx1∪⋯∪Sxi−1). We call the set {x1,…,xn}{x1,…,xn} a sequential transversal of SS, and we let TSTS be the set of all sequential transversals of SS, which includes 0̸0̸ as well. We examine conditions under which the pair (E,TS)(E,TS) is a matroid. We show that (E,TS)(E,TS) is a matroid iff TS=Tb(max(TS))TS=Tb(max(TS)) where b(max(TS))b(max(TS)) denotes the blocker of the maximal sets of TSTS. It is also shown that every matroid on a set EE can be defined as a pair (E,TS)(E,TS) where TSTS is order-independent  ; that is, the elements in any sequential transversal can be picked in any order. Various conditions and examples are provided in which (E,TS)(E,TS) is a matroid.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 28, Issue 1, January 2007, Pages 469–480
نویسندگان
, ,