TR-2005-03

Uniform partitioning to bases in a matroid

Zsolt Fekete, Jácint Szabó



Abstract

We say that a matroid M is k-uniform if - provided that it is the disjoint union of its two bases - for any given k-element subpartition P of its ground set, M can be partitioned into two disjoint bases B_1, B_2 such that ||B_1 \cap R| - |B_2 \cap R|| \leq 1 for all R \in P. The circuit matroid of an undirected graph G is called k-star-uniform if the above holds for all k-element subpartitions containing stars of independent vertices of G. In this paper we prove that the circuit matroids are 1-uniform and 3-star-uniform but not necessarily 2-uniform and 4-star-uniform.


Bibtex entry:

@techreport{egres-05-03,
AUTHOR = {Fekete, Zsolt and Szab{\'o}, J{\'a}cint},
TITLE = {Uniform partitioning to bases in a matroid},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-03}
}


Last modification: 23.11.2014. Please email your comments to Jácint Szabó!