Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski
Jácint Szabó · SIAM Journal on Discrete Mathematics · 2008
In 1981 András Recski conjectured that, if given a number $q\in \mathbb{N}$, a linearly represented matroid M, a partition $S_1 \mathbin{\dot{\cup}} \cdots \mathbin{\dot{\cup}} S_n$ of a subset of its ground set S into classes of size k, and a prescription $A\subseteq \{0,1,\dots,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\leq i\leq n$, if one exists. In this paper we prove 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 Sebő. We give an application to rigidity theory and another one to the unique solvability of linear networks containing memoryless multiports.