2
$\begingroup$

Given: a finite set $E$ and a set family $\mathscr{F} \subseteq 2^E = \mathscr{P}(E)$.

Every source known to me gives these as the first two axioms for $\mathscr{F}$ to be a family of matroid flats:

  1. $E \in \mathscr{F}$.
  2. $F_1, F_2 \in \mathscr{F} \implies F_1 \cap F_2 \in \mathscr{F}$.

Question: (a) What is the correct form for the third axiom? Can it be stated precisely?

(b) What is the conclusion of the third axiom when applied to $E \in \mathscr{F}$?

E.g. how should one understand "the empty set partitions the empty set"? Isn't the empty union equal to $\emptyset$, not to $E$? And if the third axiom makes no sense when applied to $E$, and $E \in \mathscr{F}$ is only included so that $\mathscr{F}$ isn't empty, then why not say $E \not\in \mathscr{F}, \mathscr{F} \not= \emptyset \subseteq 2^E$?


Wikipedia says: 3. If $F \in \mathscr{F}$, then the set of all $G \in \mathscr{F}$ which cover $F$ (meaning that $G \supsetneq F$ but there is no $H \in \mathscr{F}$ between $F$ and $G$) partition the elements of $E \setminus F$.

Encyclopedia of Mathematics gives two supposedly equivalent forms:
3.(a) If $G_1, \dots, G_k \in \mathscr{F}$ is the family of flats which cover $F \in \mathscr{F}$ (i.e. each $G_i$ contains $F$ properly with no $H \in \mathscr{F}$ in between), then $G_1 \setminus F, \dots, G_k \setminus F$ partition $E \setminus F$.
3.(b) For all $F \in \mathscr{F}$, $\bigcup \{ F' \in \mathscr{F}: F' \succ F \} = E$.

Oxley says: If $F \in \mathscr{F}$ and $\{ G_1, G_2, \dots, G_k\}$ is the set of minimal members of $\mathscr{F}$ that properly contain $F$, then the sets $G_1 \setminus F, G_2 \setminus F, \dots, G_k \setminus F$ partition $E \setminus F$. These notes parrot this.

Gordon, McNulty say the same thing as the first axiom given by the Encyclopedia of Mathematics, except that they don't even bother to try to explain what "cover" means.


Attempt: Are either of these definitions of the "flat cover" correct?
(a) $cover: \mathscr{F} \to 2^{2^E}$, $cover: F \mapsto \{G \in \mathscr{F}: G \supsetneq F, \forall H \in \mathscr{F}, F \subseteq H \subseteq G \implies H = F \lor H = G \}$
(b) $cover: \mathscr{F} \to 2^{2^E}$, $cover: F \mapsto \{G \in \mathscr{F}: G \supsetneq F, \forall X \in 2^E, F \subsetneq X \subsetneq G \implies X \not\in \mathscr{F} \}$

EDIT: What I had here before was totally wrong (among other things, it should be $G \setminus F$, not $E \setminus G$). Also the definitions of cover incorrectly said $G \supseteq F$ instead of $G \supsetneq F$.

Then define $[cover(F) \setminus F] \in 2^{2^E}$ by $[cover(F) \setminus F] := \{ G \setminus F: G \in cover(F) \}$.

My understanding of "partition" is the following:

$[cover(F) \setminus F]$ partitions $E \setminus F$ $\iff$ $\bigsqcup\limits_{G \in cover(F)} G \setminus F = E \setminus F$, where $\bigsqcup$ denotes disjoint union.

EDIT: What follows is also totally incorrect and based on a false premise. We're interested in $G \setminus E$ (which does not exist because $cover(E) = \emptyset$), not in $E \setminus E$, which does exist but is the empty set. I.e. using the right definition $cover(F) \setminus F$ it is an empty union, using the wrong definition $E \setminus cover(F)$ it is a non-empty union of empty sets.

When $F = E$, we should have that $E \setminus F = \emptyset$, so $$ \bigsqcup\limits_{X \in cover(F)} E \setminus X = \emptyset \,,$$ thus this is supposed to be either an empty union, or a non-empty union of empty set(s).

If it is supposed to be an empty union, then we should have that $cover(E) = \emptyset$. If it is supposed to be a non-empty union of empty set(s), we should have that $cover(E) = \{ E \}$.

In particular, should we have that $cover(E) = \{ E \}$ or $cover(E) = \emptyset$?

Using definition (a), $cover(E) = \{E\}$, (b) is supposed to be equivalent to (a), so to get $cover(E) = \emptyset$ one needs to change $H = F \lor H = G$ in the definition of (a) to $H = G$ or something else entirely.

$\endgroup$

1 Answer 1

1
$\begingroup$

Neither of your definitions of "cover" is correct, because you seem to have forgotten about the requirement that $G$ strictly contains $F$. If $F,G\in\mathscr{F}$, then $G$ covers $F$ if $F\subsetneq G$ and there does not exist any $H\in\mathscr{F}$ such that $F\subsetneq H\subsetneq G$.

The third axiom can then be stated as follows. For any $F\in\mathscr{F}$ and any $x\in E\setminus F$, there exists a unique $G\in\mathscr{F}$ such that $G$ covers $F$ and $x\in G$. In other words, every element of $E\setminus F$ is in $G\setminus F$ for a unique $G$ which covers $F$, so the collection of such sets $G\setminus F$ is a partition of $E\setminus F$.

In the case $F=E$, there is nothing special going on. There do not exist any $x\in E\setminus F$, so the requirement is vacuous. There are also does not exist any $G\in\mathscr{F}$ which covers $F$ (since there is no element of $\mathscr{F}$ which properly contains $F$), but that is fine, since the empty set is a partition (the only partition!) of the empty set.


Note that actually the uniqueness requirement here can be omitted. If $G$ and $H$ both cover $F$ and $x\in G,H$, then $G\cap H\in\mathscr{F}$ by the second axiom. We have $F\subsetneq G\cap H \subset G$ (the first inclusion is strict since $x\in G\cap H$), so $G\cap H=G$ since $G$ covers $F$. Similarly, $G\cap H=H$, so $G=H$.

So it suffices to assume the union of all the elements of $\mathscr{F}$ which cover $F$ contains all of $E\setminus F$. This is almost the same as requiring that the union of all the elements of $\mathscr{F}$ which cover $F$ is $E$ itself, which is what the second definition in the Encyclopedia of Mathematics says. Indeed, as long as there exists some element which covers $F$, then the union always contains $F$, so all that matters is whether it contains $E\setminus F$. However, when $F=E$, there is nothing that covers $F$. So the second definition in the Encyclopedia of Mathematics is incorrect and should be modified to only apply when $F\neq E$.

$\endgroup$
2
  • $\begingroup$ This is very helpful, especially the sanity check that something was fishy about the 2nd Encyclopedia of Mathematics definition. I really appreciate you taking all of the time to explain this. 2 questions to confirm my understanding: (1) Would either of the above two proposed "definitions" of cover be correct if $G \supseteq F$ was replaced with $G \supsetneq F$? Or are they more deeply flawed than that? (2) If $F \in \mathscr{F}$ is a hyperplane, then its cover is $E$, right? Since it is a maximal proper flat? So a flat has an empty cover if and only if it is $E$? $\endgroup$ Nov 26, 2017 at 2:04
  • 1
    $\begingroup$ (1) Yes, both your definitions are correct with that correction. (2) Yes, that's correct. $\endgroup$ Nov 26, 2017 at 3:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .