Lukas' Notes

Search titles, aliases and note text. Use # for tags.

Basis Family (Matroid)

5 min read

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 be a finite set and a family of subsets of satisfying three axioms:

  1. Non-emptiness: .
  2. Equal cardinality: For all , it holds that .
  3. Basis exchange: For all and all , there exists such that .

Any such family is the set of bases of a unique matroid on , whose independent sets are exactly the subsets of elements of .

Relation to the independent-set axioms

The basis-family axioms are equivalent to the independent-set axioms. Given a matroid , its bases are the maximal independent sets, and they satisfy non-emptiness, equal cardinality, and basis exchange. Conversely, given a basis family , the corresponding independence family is

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

is a matroid

is a matroid.

is a matroid

Proof that is in fact a matroid.

Non-emptiness

Given that , we know that there exists some . Trivially, the empty set is subset of any set, i.e., .

Hence,

i.e., is non-empty.

Heredity

Every subset of some is also in . Therefore, is hereditary.

Exchangeability

Fix two bases with their subsets and , whereby we force .

Basis exchange allows us to take one and one and exchange them, i.e.,

Basis exchange allows us to decide which is exchanged to . Therefore, we only exchange that are not in , i.e., . Let’s do that repeatedly, i.e.,

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

Therefore, only contains elements from or , i.e.,

Further, we haven’t removed any from . Given that , we know that

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

Given that , we can safely conclude that

Also, we know that every basis has equal cardinality. Therefore

Substituting into the above yields

We know even more. We know that

Missing \end{aligned}\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}

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

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

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

\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}

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

\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),

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

Examples

Uniform matroid

Let and

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

Backlinks