1
$\begingroup$

Say we have a matroid on a finite set $X$. The collection of its flats forms a geometric lattice under $\subseteq$, where the join is given by intersection.

This question is about the converse to that fact.

Now usually the converse is stated like this:

Every geometric lattice is the lattice of flats of some matroid.

What that really means is that every geometric lattice is isomorphic to the lattice of flats of some matroid. So that's fine, but:

What about when the lattice is already given as a collection of sets under $\subseteq$ with join given by intersection? If this lattice is geometric, must that collection of sets form the flats of a matroid?

No. For example, we could take the collection $$\{ \emptyset, \{1\}, \{2\}, \{1,2,3\} \}.$$ So what additional conditions are necessary to make a converse of this form true? In other words, I am looking for a biconditional of this form:

Desired Theorem. Suppose $\mathcal C$ is a collection of subsets of a finite set $X$ that is closed under intersection. (And here we consider $X$ itself to be the trivial “intersection of no sets” so it is included too.) Let $L$ be the lattice under $\subseteq$ whose elements are the sets of $\mathcal C$. Then $\mathcal C$ is the collection of flats of some matroid on $X$ if and only if $L$ is geometric and ____.

So what goes in the blank?

Let me give one answer. To back things up for a second, the condition stated on $\mathcal C$ (of its being closed under intersection) already implies the first two axioms for the flats of a matroid (since we are including $X$ itself as a sort of degenerate intersection, at least). So we need only account for the third axiom, which says that if we consider any $S\in \mathcal C$, each element of $X\setminus S$ occurs in exactly one of the sets covering $S$ in the poset $(\mathcal C,\subseteq)$.

So we could just put that in the blank. But that is not very revealing. That is, it's so powerful that it totally obviates anything we know about the lattice $L$ being geometric. And the real question here is, what is the weakest additional thing we can know that is sufficient?

Now I can think of one answer. We could put in the blank the condition that this third axiom holds but just for the atoms of $L$. In other words, letting $0_L$ be the minimal element of $L$, we require that each element of $X\setminus 0_L$ is contained in a unique atom (i.e., set covering $0_L$). So that's the third axiom above, but applied only with $S=0_L$.

In other words, we have this theorem:

Theorem. Suppose $\mathcal C$ is a collection of subsets of a finite set $X$ that is closed under intersection (and includes $X$). Let $L$ be the lattice given by $(\mathcal C,\subseteq)$. Then $\mathcal C$ is the collection of flats of some matroid on $X$ if and only if $L$ is geometric and the union of the atoms of $L$ is $X$.

Proof. For the forward direction, it is a standard theorem that $L$ is geometric, and the third axiom for flats gives the additional condition.

For the converse, we have to show that $\mathcal C$ satisfies the three axioms for the flats of a matroid. Two of these follow since the collection is closed under intersection and contains $X$. For the third, take any $S \in \mathcal C$ and $x \in X \setminus S$. We just need to show that some set $E$ covering $S$ contains $x$. (The uniqueness of this set follows from considering the intersection of all such sets.)

To this end, let $A$ be some atom with $x \in A$ and let $E=A\vee S$. Since $L$ is geometric, it is semimodular. As a result, the fact that $A$ covers $0_L$ implies that $A\vee S=E$ covers $0_L\vee S=S$.

Now my actual questions are as follows.

  1. Does the above really give the best way to fill in the blank in the Desired Theorem?
  2. Is there someplace in the literature I can find this stated and proved? It seems like a basic enough question for this to be reasonable, but it also seems like every reference I look in is content to say that a geometric lattice is isomorphic to the lattice of flats of a matroid, without respecting if that original lattice is already given by a system of sets.
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.