Uniform partitioning to bases in a matroid

Zsolt Fekete, Jácint Szabó


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:

AUTHOR = {Fekete, Zsolt and Szab{\'o}, J{\'a}cint},
TITLE = {Uniform partitioning to bases in a matroid},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-03}

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