TR-2010-10

On disjoint common bases in two matroids

Nicholas J. A. Harvey, Tamás Király, Lap Chi Lau

Published in:
SIAM Journal on Discrete Mathematics 25 (2011), 1792-1803.



Abstract

We prove two results on packing common bases of two matroids. First, we show that the computational problem of common base packing reduces to the special case where one of the matroids is a partition matroid. Second, we give a counterexample to a conjecture of Chow, which proposed a sufficient condition for the existence of a common base packing. Chow's conjecture is a generalization of Rota's basis conjecture.


Bibtex entry:

@techreport{egres-10-10,
AUTHOR = {A. J., Nicholas and Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap},
TITLE = {On disjoint common bases in two matroids},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2010},
NUMBER = {TR-2010-10}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!