# Struggling with the definition of rank for a independent system/matroid

Let $U = (E, I)$ be an independent system (not a matroid). A base $B$ of $E$ is a maximal independent set.

$(E, I) = (\{1,2,3,4\}, \{\{\emptyset, \{1\}, \{2\}, \{3\}, \{2, 3\}, \{1, 2\},\{4\}\}$

Bases = $\{\{2,3\}, \{1,2\}, \{4\}\}$ which are also in $I$ and also $\{\{1,3\}\}$ (it's not a circuit since $U$ is not a matroid, correct me on this one).

The definition of a rank, according to my lecture:

Lower rank of a system $r_-(U) = min \{|B| : B$ is base of $U$$\} Upper rank of a system r_+(U) = max \{|B| : B is base of U$$\}$

rank quotient $\rho=\frac{r_-(U)}{r_+(U)}$ which equals to $1$ for a matroid

taking min and max cardinality over the Bases

$r_-(U) = 1$

$r_+(U) = 2$

What did I miss here? I believe the bases are wrong ?

You don't know that every basis has maximum size, at least not simply because you're maximizing each time. As an instructive example to what might be going on, let's say I had two ladders, one with four rungs and the other with seven. I want to go as high as possible, but I can't look up. If I step first on the shorter ladder, I'll end up at the top after four rungs and say "okay, I'm done! I can't go any higher." In the analogy, here the upper and lower ranks would be 4 and 7.

(I'm trying to think of a real example right now)

• is it the same as trying to find a maximal matching vs a maximum matching ? or how did you find the ranks ?
– Oleg
Mar 26 '18 at 20:38
• In this analogy, how do you know that the ladders don't share a common rung? For example consider an independence system with bases 12 and 234 . Then two "ladders" (a.k.a., chains in the face lattice of the corresponding simplicial complex) are given by $\emptyset \subset 2 \subset 12$ and $\emptyset \subset 2 \subset 23 \subset 234$. The first rung of both ladders is the element 2, so after the first step the base we will reach has not been determined. Mar 27 '18 at 14:16

In short: you are right to believe that you computed the bases wrong. The bases are the sets $4,12$, and $23$ (more on this below). Nonetheless, you obtained the correct upper and lower ranks for this example. Since there quotient isn't $1$, you proved that this independence system is not pure (defined below) and hence is not a matroid.

Now let's take a deeper look:

There are some technicalities in the definitions that are being swept under the rug in the OP. Taking a closer look at them might help to clarify the situation.

We start with an independence system $U = (E, I)$ on the ground set $E = \{1,2,3,4\}$ and $I = \{\emptyset, 1,2,3,4,12,23\}$. (We're being a little sloppy writing, e.g., 12 for the set $\{1,2\}$ but hopefully that isn't too confusing.)

A base of $U$ is a maximally independent set, where "maximally" means maximal with respect to set inclusion. Notice that this definition depends both on $E$ and on $I$. So the bases of $U$ are$~~4,12$, and $23$ since (1) each of these sets is in $I$ and (2) there is no set in $I$ that properly contains any of these. Notice that $13$ is not a base since it does not satisfy property (1).

An independence system is called pure if the set $\{\#B~|~B \text{ a base }\}$ is a singleton (i.e., if all bases have the same cardinality). Since $U$ has bases of size one and two, it is not pure.

Also if we think of a matroid as its set of independent sets (this is just one of many ways to think of a matroid), then there is the following chain of inclusions

$$\text{independence systems } \supsetneq \text{ pure independence systems } \supsetneq \text{ matroids}.$$

The example $U$ from the OP provides an independence system that is not pure. The independence system on $\{1,2,3,4\}$ consisting of all subsets of the sets $\{1,2\}$ and $\{3,4\}$ is a pure independence system (it has two bases and both have size two) but it is not a matroid.

• Unterstood :) Any idea why @MCT would say that lower rank = 4 and upper = 7 instead of 1 and 2 ?
– Oleg
Mar 27 '18 at 13:32
• Yup. The example in @MCT's analogy has nothing to do with the example in the OP. Instead it suggests an algorithmic way to find the bases of an independence system: (1) Start by taking $B = \emptyset$. (2) If $B$ is not maximal in $I$ (w.r.t. set inclusion) then choose any $i \in E$ so that $B = B \cup \{i\} \in I$; else stop and B is a base. Repeat (2) until you obtain a base. Mar 27 '18 at 13:59