Simple question. I think I'm missing something. Matroids.

52 Views Asked by At

Lemma : Given a matroid $\mathcal{M} = (N, \mathcal{I})$, and a vector $x \in [0, 1]^N$, suppose that the sets $A, B$ are tight in $x$, i.e $x(A) = r(A)$ and $x(B) = r(B)$ where $r$ denotes the rank function. Then $A\cup B, \, A\cap B$ are also tight in $x$.

Is this a Counterexample??

$\mathcal{I} = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}\}$ and $x = (1, 1, 1)$. Let $A = \{1, 2\}$ and $B = \{2, 3\}$. Then $x(A) = 2 = r(A)$ and $x(B) = 2 = r(B)$ but $x(A\cup B) = 3$ while $r(A \cup B) = 2$.

For the definitions and the original statement of the lemma, see https://thibaut.horel.org/submodularity/notes/02-24.pdf

Rank function : $r(A) = \max_{I \in \mathcal{I}} |A\cap I|$

1

There are 1 best solutions below

0
On BEST ANSWER

The lemma assumes that $x$ is an element of the matroid polytope $P(\mathcal M)$; this is false for your example precisely because $x(\{1,2,3\}) = 3$ but $r_{\mathcal M}(\{1,2,3\}) = 2$.

As shown in the notes you link to, if $A$ and $B$ are tight with respect to $x$, then $$x(A \cup B) + x(A \cap B) \ge r_{\mathcal M}(A \cup B) + r_{\mathcal M}(A \cap B)$$ and this holds without any other assumptions on $x$. If, furthermore, $x \in P(\mathcal M)$, then we also know that $$x(A \cup B) \le r_{\mathcal M}(A \cup B) \text{ and } x(A \cap B) \le r_{\mathcal M}(A \cap B).$$ This is compatible with the previous inequality only if none of the inequalities are strict, so $x(A \cup B) = r_{\mathcal M}(A \cup B)$ and $x(A \cap B) = r_{\mathcal M}(A \cap B)$, finishing the proof of the lemma.