A matroid with zero Euler characteristic has an isthmus

98 Views Asked by At

Let $M$ be a rank $r$ matroid on the ground set $E$. $e\in E$ is said to be an isthmus of $M$ if $e$ is contained in every base of $M$. We also define the Euler characteristic of $M$ to be $$\chi(M)=\sum_{i=0}^r(-1)^{i-1}f_i$$ where $f_i$ denotes the number of independent sets of $M$ that have cardinality $i$. This definition also makes sense for simplicial complexes and it is one less than the usual definition, since we also count the empty set.

It is not hard to see that, if $M$ has an isthmus $e$, then $\chi(M)=0$. This can be proved by partitioning the independent sets of $M$ as those that contain $e$ and those that do not contain $e$. If I recall correctly, this is true in general for simplicial complexes.

My question is: does the converse hold? That is, if$\chi(M)=0$, does $M$ have an isthmus? This is not true for simplicial complexes, so I was wondering if it is true for matroids.

1

There are 1 best solutions below

1
On

I apologize for my previous erroneous answer. I now think the claim is correct.

We argue the following by induction.

Proposition: If a matroid $(X, I)$ has rank $r$, then $(-1)^r\chi(I) \geq 0$, with equality iff $I$ has a isthmus.

Proof: We argue by induction on $|I|$. If $|I|= 1$ the result is trivial.

Suppose now that the results holds for all matroids of smaller size than $I$. If $I$ has a isthmus, the result is already shown in the question.

Otherwise, pick any $e \in X$ such that $\{e\} \in I$. We form two families $$I_1 = \{X \in I: e \notin X\}.$$ $$I_2 = \{X \backslash\{e\}: X \in I, e \in X\}.$$ These two families should also be matroids. Furthermore, as $e$ is not an isthmus, $I_1$ has rank $r$ and $I_2$ has rank $r - 1$. Thus, we can check that $$(-1)^r \chi(I) = (-1)^{r}\chi(I_1) + (-1)^{r - 1}\chi(I_2) \geq 0$$ as both summands are non-negative by induction hypothesis.

To show that equality cannot hold, note that if $\chi(I) = 0$, then $\chi(I_1) = \chi(I_2) = 0$. By the induction hypothesis, $I_2$ must have an isthmus $g$. We now show that $g$ must be an isthumus of $I$. Indeed, if some basis $X$ does not contain $g$, then the base exchange property says that there exists some basis $Y$ such that $e \in Y \subset X \cup \{e\}$, so $Y \in I_2$ does not contain $g$, contradiction.

I apologize in advance if the answer is still erroneous, as I have not worked extensively with matroids.