کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649923 1342469 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The max-flow min-cut property of two-dimensional affine convex geometries
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The max-flow min-cut property of two-dimensional affine convex geometries
چکیده انگلیسی

In a matroid, (X,e)(X,e) is a rooted circuit if X is a set not containing element e   and X∪{e}X∪{e} is a circuit. We call X a broken circuit of e  . A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189–222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q6Q6. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 9, 6 May 2008, Pages 1674–1689
نویسندگان
, ,