# A matroid parity exchange property

As part of my research, I encountered the following problem. Let $$M = (E,I)$$ be a matroid and let $$P = \{P_1,\ldots,P_n\}$$ be a partition of $$E$$ into (disjoint) pairs. For $$A \subseteq P$$, we say that $$A$$ is "feasible" if the union of elements in $$A$$ is an independent in the matroid: $$E(A) = \bigcup_{P_i \in A} P_i \in I$$.

Question: Let $$X,Y \subseteq P$$ be two feasible sets of pairs, and let $$k \in \mathbb{N}$$; for simplicity, assume that $$|Y| = m$$ and that $$k$$ divides $$m$$. Can we always find a partition $$X_1,\ldots, X_k$$ of $$X$$ and $$Y_1,\ldots, Y_k \subseteq Y$$ such that the following holds:

(1) (Exchange) $$(Y \setminus Y_i) \cup X_i$$ is feasible, i.e., $$E((Y \setminus Y_i) \cup X_i) \in I$$ for all $$i = 1,\ldots,k$$.

(2) (Almost a Partition) There is $$S \subseteq Y, |S| \leq 2 \cdot k$$, such that every pair $$p \in Y \setminus S$$ appears at most once in $$Y_1,\ldots, Y_k$$ and every pair $$q \in S$$ appears at most twice in $$Y_1,\ldots, Y_k$$.

Intuition: The reason I conjectured the above is that for special cases of matroid, the statement seems to be correct. For example, consider the case of a partition matroid, where the set of elements $$E$$ is partitioned into disjoint subsets $$C_1,\ldots, C_r$$ (call them colors) and the independent sets $$I$$ are all sets $$F \subseteq E$$ such that $$|F \cap C_i| \leq 1$$ for $$i = 1,\ldots,r$$. Given the feasible sets of pairs $$X,Y$$, we can construct $$Y_1,\ldots, Y_k$$ and $$X_1,\ldots, X_k$$ as follows. Assume for simplicity that $$|E(X)| = |E(Y)| = r$$, i.e., both $$X$$ and $$Y$$ have one element from each color; moreover, assume that $$X \cap Y = \emptyset$$ or the problem would be easier. The construction is as follows.

Choose an arbitrary pair $$x_1$$ and place it in $$X_1$$; then, choose $$y_1$$ such that $$y_1,x_1$$ have a mutual color (there is such $$y_1$$) and place $$y_1$$ in $$Y_1$$. Then, select $$x_2$$ that also has a mutual color with $$y_1$$ (the color of the other element in the pair $$y_1$$) and place $$x_2$$ also in $$X_1$$. Then, choose $$y_2$$ with a mutual color to $$x_2$$. Continue with this process of producing an interleaving chain $$x_1,y_1,\ldots, x_k,y_k$$ until reaching $$X_1 = \{x_1,\ldots, x_k\}$$. Observe that we only need to add one extra pair $$y'_1$$ with a mutual color with $$x_1$$ to $$Y_1$$ to ensure that $$(Y \setminus Y_1) \cup X_1$$ is feasible. Then, we create $$X_2,Y_2$$ where in $$X_2$$ we do not take pairs from $$X_1$$, and for $$Y_2$$ we may need to take only one pair that appeared in $$X_1$$. Similarly, we can create all sets $$X_2,Y_2,\ldots,X_k,Y_k$$, where for each set $$Y_i$$ there is only one pair $$y'_i$$ that appears also in one other set $$Y_j$$ (we therefore have property (2) with at most $$k$$ pairs).

The above construction is easy as the matroid has a specific form, in which all cycles are of size 2. I suspect that for general matroids it is still possible to have this result possibly with a more global construction. Any help would be greatly appreciated.

• You can assume that $|X| = m$. The $X_i$ form a partition, but the $Y_i$ may only be an "almost partition", meaning that up to $2 \cdot k$ pairs from $Y$ appears twice (as in my construction for partition matroid).
– John
Feb 15 at 6:22