1
$\begingroup$

Let $M$ be a matroid. (Assume that $M$ is a graphic matroid if it helps.) Let $M^2 = M \vee M$ be a union of $M$ by itself. See e.g. this lecture note for the definition of matroid union.

From the definition of matroid union, we have the following: There is a fixed partitioning $P$ of all independent sets of $M^2$ such that for any independent set $I$ of $M^2$, we have $P(I) = (I_1,I_2)$ where $I_1$ and $I_2$ are disjoint independent sets of $M$.

Is there a partition $P$ that also has the additional "robustness" property below?

For any two independent sets $I$ and $I'$ where the size of symmetric difference $|I \triangle I'|$ is small, say at most 2, we have both $|I_1 \triangle I'_1|$ and $|I_2 \triangle I'_2|$ are small, say at most some constant.

$\endgroup$
5
  • $\begingroup$ If by $k$-fold sum you mean the direct sum of $k$ copies of $M$, then the property in the second paragraph isn't quite true: Each $I_i$ is an independent of the $i^\text{th}$ copy $M_i$ of $M$, and not of $M$ itself. That said, given an independent set $I$ of $M^k$ one still has the partition $P(I) = (I_1, \dots, I_k)$ where for all $i,j$ (1) $I_i$ is independent in $M_i$ and (2) $I_i \cap I_j = \emptyset$ (since the ground sets of $M_i$ and $M_j$ are disjoint). It seems the strong form of your robustness property follows easily once this confusion is cleared up. $\endgroup$
    – Aaron Dall
    Feb 6, 2018 at 7:31
  • $\begingroup$ @AaronDall I did not mean that it is a direct sum of $k$ copies of $M$. Thanks for asking. I did not know that this is not a standard definition, and I will clarify my question accordingly. But the definition is the following: Let $M$ be a matroid with a ground set $S$. An independent set of $k$-fold sum $M^k$ is a subset $I$ of $S$ where $I$ can be partitioned into $k$ parts such that each part is an independent set of $M$. $\endgroup$
    – eig
    Feb 6, 2018 at 9:57
  • 2
    $\begingroup$ I think, it is usually called 'matroid union', not 'sum', see en.wikipedia.org/wiki/Matroid#Sums_and_unions $\endgroup$ Feb 6, 2018 at 11:28
  • $\begingroup$ what exactly is your question (or, better to say, two questions): does such a $P$ always exist? $\endgroup$ Feb 6, 2018 at 11:30
  • $\begingroup$ @FedorPetrov Thank you. I agree that the term "matroid union" is more standard. I edited my question accordingly. I also simplified it a bit. $\endgroup$
    – eig
    Feb 6, 2018 at 21:40

0

Your Answer

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

Browse other questions tagged or ask your own question.