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.

  • $\begingroup$ 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). $\endgroup$
    – John
    Feb 15 at 6:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.