Proof of matroids

Question

We have set $S$ and subset $I = 2^S \setminus \{S\}$. Show that $M=(S,I)$ is a matroid.
Is it graphic, linear or a matching matroid?

I am little struggling how to prove this, there should be 3 things to prove.

• $\varnothing\in I$
• if $i \in I$ and $j \subseteq i$, then $j \in I$
• if $i,j \in I$ and $|i|<|j|$, then $i+x \in I$ for some $x \in j\setminus i$

Any ideas how to prove that, the $2^S$ is kinda making me confused in the prove.

Answer 1

$2^S$ is the power set of $S$, i.e., the collection of all subsets of $S$. We’re throwing away $S$ itself, the biggest of these subsets, so $I$ is the collection of all proper subsets of $S$. You could write $$I=\{i\subseteq S:i\ne S\}\;.$$

If, for example, $S=\{0,1,2\}$, then $I=\big\{\varnothing,\{0\},\{1\},\{2\},\{0,1\},\{0,2\},\{1,2\}\big\}$: it contains $7$ of the $2^3=8$ subsets of $S$ $-$ all of them except $S=\{0,1,2\}$ itself.

It’s automatic, therefore, that $\varnothing\in I$ (provided that $S$ is non-empty, which I’m sure you’re intended to assume). The hereditary property, which I’ll leave to you, is also automatic. The augmentation property isn’t much harder. Suppose that $i,j\in I$ with $|i|<|j|$. Then there is certainly some $x\in j\setminus i$; let $i'=i\cup\{x\}$. To show that $i'\in I$, you need to show that $i'\ne S$. But $|i'|=|i|+1\le|j|$ (why?), so ... ?

Some hints for the second part of the question:

1. Consider the cycle graph on $|S|$ vertices. It has $|S|$ edges; what’s the only set of edges that is not a forest?

2. Let $n=|S|-1$. For $k=1,\dots,n$ let $e_k$ be the unit vector in $\Bbb R^n$ that has a $1$ in the $k$-th componenet and $0$ everywhere else, and let $e_0=\langle\underbrace{1,1,\dots,1}_n\rangle$. Let $S=\{s_0,s_1,\dots,s_n\}$, and define $h:S\to\Bbb R^n:s_k\mapsto e_k$. What subsets of $\{e_0,e_1,\dots,e_n\}$ are linearly independent?

3. The rank of a matching matroid is always even. The cycle graphs are useful here, too; consider $C_n$ for even and odd $n$ separately.