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

Question

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 ?

Answer 1

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.

Answer 2

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)