|
In 1981 András Recski conjectured that if we are given a number q\in N, a linearly represented matroid M, a subpartition S_1 \cup ... \cup S_n of its ground set S into classes of size k, and a prescription A\subseteq {0,1,...,k} without two consecutive gaps, then one can find in polynomial time an independent set F of M of size q such that |F \cap S_i|\in A for all 1 <= i <= n, if one exists. In this paper we prove the this conjecture. The proof is based on Lovász' result on the polynomial solvability of the matroid parity problem for linearly represented matroids, and on an important technique about jump systems, proved by Sebo. We give an application to rigidity theory, and another one to the unique solvability of linear networks containing memoryless multiports.
Bibtex entry:
| AUTHOR | = | {Szab{\'o}, J{\'a}cint}, |
| TITLE | = | {Matroid parity and jump systems: a solution to a conjecture of Recski}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-09} |