0
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ is it the same as trying to find a maximal matching vs a maximum matching ? or how did you find the ranks ? $\endgroup$
    – Oleg
    Mar 26 '18 at 20:38
  • $\begingroup$ 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. $\endgroup$
    – Aaron Dall
    Mar 27 '18 at 14:16
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Unterstood :) Any idea why @MCT would say that lower rank = 4 and upper = 7 instead of 1 and 2 ? $\endgroup$
    – Oleg
    Mar 27 '18 at 13:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Aaron Dall
    Mar 27 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.