Basis Family (Matroid)

Definition

Basis Family

A matroid can also be defined directly through its bases, without first specifying the independent sets. The collection of bases itself satisfies three axioms.

Let $E$ be a finite set and $\mathcal{B}$ a family of subsets of $E$ satisfying three axioms:

1. Non-emptiness: $\mathcal{B}\ne \varnothing$.
2. Equal cardinality: For all $B_1,B_2\in \mathcal{B}$, it holds that $|B_1|=|B_2|$.
3. Basis exchange: For all $B_1,B_2\in \mathcal{B}$ and all $x\in B_1\setminus B_2$, there exists $y\in B_2\setminus B_1$ such that $(B_1\setminus \{x\})\cup \{y\}\in \mathcal{B}$.

Any such family $\mathcal{B}$ is the set of bases of a unique matroid on $E$, whose independent sets are exactly the subsets of elements of $\mathcal{B}$.

Relation to the independent-set axioms

The basis-family axioms are equivalent to the independent-set axioms. Given a matroid $M=(E,\mathcal{I})$, its bases are the maximal independent sets, and they satisfy non-emptiness, equal cardinality, and basis exchange. Conversely, given a basis family $\mathcal{B}$, the corresponding independence family is

$$\mathcal{I}=\{X\subseteq E\mid X\subseteq B\text{ for some }B\in \mathcal{B}\}.$$

Axiom equal cardinality corresponds to the consequence of exchangeability that all bases have the same size. Axiom basis exchange is a basis-level form of exchange: instead of extending a smaller independent set, it swaps an element between two equal-size bases.

Matroid

$\mathcal{M}=(E,\mathcal{I}(\mathcal{B}))$ is a matroid

$\mathcal{M}=(E,\mathcal{I}(\mathcal{B}))$ is a matroid.

$\mathcal{M}=(E,\mathcal{I}(\mathcal{B}))$ is a matroid

Proof that $\mathcal{M}=(E,\mathcal{I}(\mathcal{B}))$ is in fact a matroid.

Non-emptiness

Given that $\mathcal{B}\ne \varnothing$, we know that there exists some $B\in \mathcal{B}$. Trivially, the empty set is subset of any set, i.e., $\varnothing \subseteq B$.

Hence,

$$\varnothing \in \mathcal{I}(\mathcal{B})=\{I\mid \exists B\in \mathcal{B}:I\subseteq B\},$$

i.e., $\mathcal{M}$ is non-empty.

Heredity

Every subset of some $B\in \mathcal{B}$ is also in $\mathcal{I}(\mathcal{B})$. Therefore, $\mathcal{M}$ is hereditary.

Exchangeability

Fix two bases $B_1,B_2\in \mathcal{B}$ with their subsets $X\subseteq B_1$ and $Y\subseteq B_2$, whereby we force $|X|<|Y|$.

Basis exchange allows us to take one $x\in B_1\setminus B_2$ and one $y\in B_2\setminus B_1$ and exchange them, i.e.,

$$\begin{array}{rl}{B}_1^{\prime }& =(B_1\setminus \{x\})\cup \{y\},B_1^{\prime }\in \mathcal{B}\\ B_2^{\prime }& =(B_2\setminus \{y\})\cup \{x\},B_2^{\prime }\in \mathcal{B}\end{array}$$

Basis exchange allows us to decide which $x\in B_1\setminus B_2$ is exchanged to $B_2$. Therefore, we only exchange $x$ that are not in $X$, i.e., $x\notin X$. Let’s do that repeatedly, i.e.,

$$\begin{array}{rl}{B}_1^{\prime }& =(B_1\setminus \{x\})\cup \{y\},x\notin X,y\in B_2\\ B_1^{\prime \prime }& =(B_1^{\prime }\setminus \{x\})\cup \{y\},x\notin X,y\in B_2\\ & ⋮\\ B_1^{(n)}& =(B_1^{(n-1)})\setminus \{x\})\cup \{y\},x\notin X,y\in B_2,\end{array}$$

until there is no $x$ to give, i.e., until

$$\nexists x\in B_1^{(n)}\setminus B_2:x\notin X⟺B_1^{(n)}\setminus (B_2\cup X)=\varnothing .$$

Therefore, $B_1^{(n)}$ only contains elements from $B_2$ or $X$, i.e.,

$$\begin{array}{rl}{B}_1^{(n)}\setminus B_2& \subseteq X\\ B_1^{(n)}\setminus X& \subseteq B_2\end{array}$$

Further, we haven’t removed any $x\in X$ from $B_1$. Given that $X\subseteq B_1$, we know that

$$X\subseteq B_1^{(n)}.$$

Consider the subset-relations we already know and their cardinalities:

$$\begin{array}{rl}{B}_1^{(n)}\setminus (B_2\cup X)=\varnothing & ⟹|B_1^{(n)}\setminus (B_2\cup X)|=0\\ B_1^{(n)}\setminus B_2\subseteq X& ⟹|B_1^{(n)}\setminus B_2|\le |X|\\ B_1^{(n)}\setminus X\subseteq B_2& ⟹|B_1^{(n)}\setminus X|\le |B_2|\end{array}$$

Given that $X\subseteq B_1^{(n)}$, we can safely conclude that

$$|B_1^{(n)}\setminus X|=|B_1^{(n)}|-|X|.$$

Also, we know that every basis $B\in \mathcal{B}$ has equal cardinality. Therefore

$$B_1^{(n)}\in \mathcal{B}⟹|B_1^{(n)}|=|B_1|=|B_2|.$$

Substituting into the above yields

$$|B_1^{(n)}\setminus X|=|B_1^{(n)}|-|X|=|B_2|-|X|.$$

We know even more. We know that

\begin{aligned} |X| < |Y| &\implies |B_{1}^{(n)} \setminus X| = |B_{2}| - |X| > |B_{2}| - |Y| \\ &\implies |B_{1}^{(n)} \setminus X| + |Y| > |B_{2}|.

\end{aligned}

Now ask the question: can we [[Knowledge/Exchangeability (Matroid)|exchange]] one $y \in Y \setminus X$ to $X$, i.e., does there exists such a $y$? Suppose not, i.e.,

B_{1}^{(n)} \setminus X \cap Y = \emptyset.

$$Thenwecouldsafelyconcludethat$$

|(B_{1}^{(n)} \setminus X) \cup Y| = |B_{1}^{(n)} \setminus X| + |Y| > |B_{2}|.

$$Butwealsoknow(forafact)that$$

B_{1}^{(n)} \setminus X \subseteq B_{2}, ; Y \subseteq B_{2} \implies (B_{1}^{(n)} \setminus X) \cup Y \subseteq B_{2}.

Therefore, $(B_{1}^{n} \setminus X) \cap Y = \emptyset$ is incorrect, leading to the conclusion that

\begin{aligned}
\exists y \in Y: y \in B_{1}^{(n)} \setminus X &\iff \exists y \in Y: y \in B_{1}^{(n)} \land y \not\in X
\
&\iff \exists y \in Y\setminus X: y \in B_{1}^{(n)}.
\end{aligned}

Therefore, we can extend $X$ by some $y \in Y \setminus X$ and still

X \cup { y } \subseteq B_{1}^{(n)}.

$$Weconcludethat$$

\forall X, Y \in E: \bigl( |X| < |Y| \implies \exists y \in Y: \underline{ \exists B’ \in \mathcal{B}:U \setminus X: X \cup { y } \subseteq B } \bigr),

and given the construction of $\mathcal{I}(\mathcal{B})$, i.e.,

\underline{ \mathcal{I}(\mathcal{B}) = { I \mid \exists B’ \in \mathcal{B}: I \subseteq B } },

we know that $\mathcal{M}$ grants [[Knowledge/Exchangeability (Matroid)|exchangeability]].

Examples

Uniform matroid $U_{2,4}$

Let $E=\{1,2,3,4\}$ and

$$\mathcal{B}=\{B\mid B\subseteq E\wedge |B|=2\}.$$

The basis family is the collection of all $2$-element subsets of $E$. It satisfies non-emptiness, since $\mathcal{B}$ is non-empty, since every basis has size $2$, and (B3) since swapping any element of one $2$-set for an element of another yields another $2$-set.