کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423524 | 1342400 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The edge covering number of the intersection of two matroids
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The edge covering number of a hypergraph A is β(A)=min{|B|:BâA,âB=âA}. The paper studies a conjecture on the edge covering number of the intersection of two matroids. For two natural numbers k,â, let f(k,â) be the maximal value of β(Mâ©N) over all pairs of matroids M,N such that β(M)=k and β(N)=â. In (Aharoni and Berger, 2006) [1] the first two authors proved that f(k,â)â¤2max(k,â) and conjectured that f(k,k)=k+1 and f(k,â)=â when â>k. In this paper we prove that f(k,k)â¥k+1, f(2,2)=3 and f(2,3)â¤4. We also form a conjecture on the edge covering number of 2-polymatroids that is a common extension of the above conjecture and the Goldberg-Seymour conjecture, and prove its first non-trivial case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 1, 6 January 2012, Pages 81-85
Journal: Discrete Mathematics - Volume 312, Issue 1, 6 January 2012, Pages 81-85
نویسندگان
Ron Aharoni, Eli Berger, Ran Ziv,