matroids axioms and independence system

Question

A finite matroid $M$ is a pair $(E,I)$ where $E$ is a finite set and $I$ is a family of independent set with the following properties:

1) There is at least an independent system

2) Every subset of an independent set is independent.

3) If $A$ and $B$ are two independent sets and $A$ has more elements than $B$. Then, there exist an element in $A$ that when we added to $B$ gives a larger independent set than $B$.

The first two properties define a combinatorial structure known as an independence system.

1. Suppose that $M$ is an independence system but not a matroid. I am wondering if there is there a canonical... or a better... or unique way to construct a matroid from $M$ ?

2. Can we express $M$ canonically in terms of given matroids? (for example, as an intersection...)

Disclaimer: This question was posted first in math stack exchange without success...

Answer 1

The substantial question 2 being already answered, I will address the less substantial 1.

Even if not substantial, the formalization of 1 might not be immediate (and at the end all the question might be considered by someone only a logical sophism, but since questions of the kind "is a canonical construction available?" arise naturally,I will answer anyway. In some cases the answer to such questions depends upon subtle corners of the formalization).

First note the following formal answer: yes, take as independent every (nonempty) subset of $E$.

It answers the question as posed (it is even the "largest" matroid extending $M$ on the same base set $E$),but it is clearly an undesired answer. It is a matroid generally too far from the initial independence system.

So let us search a "minimal" matroid extending a given independence system (minimal for set inclusion; by the substantial answer to 2 the independence system is the intersection of such matroids).

If the base set $E$ is not only a mere set, but a "list" (a finite set equipped with a total order), then again an (again unwanted, trivial) answer is available: take the first minimal matroid that extends $M$ (the first for the the "natural" order on $P(P(E))$: note that if $X$ is a totally ordered finite set, then so is also $P(X)=2^X$ with the lexicographic order).

This is again (formally correct but) unwanted since (a) no intelligent construction of the matroid is given (only a brutal "try each axiom and see"); (b) the answer depends on a (unrelated with $M$) total list order on $E$.

So one might request a request at least independence from the listing order.

Really, in general, in questions like this (can I "canonically construct" a structure of type $A$ on $E$ starting from a given structure of type $B$?) one requests "functoriality" (concrete over the base set $E$) at least for isomorphisms; in particoular, the group of transformations of $E$ that are $B$-automorphisms must also be $A$-automorphisms.

[This must be so for any kind of reasonably first order definable constructions; see Hodges, model theory. In this specific case, the structures are not directly given as first order ones, but one can cripto-equivalently define them as first order structures with a standard trick: in place of $E$, take a atomic boolean algebra (so that $E$ is identified with its atoms); a added unary predicate "independent" applied to elements of the boolean algebra permits first order translations of the axioms .(using in place of 3 the form of the exchange axiom that works also for infinite dimensional matroid lattices: the covering property)]

With this "functoriality" request to formalize "canonical", an easy example shows that in general a canonical construction is impossible:

on a set $E$ with three elements $a,b,c$ take as maximal independent sets the singleton of $a$ and the pair of $b,c$. To minimally extend to a matroid one has to take as basis besides $b,c$ also either $c,a$ or $a,b$.

(think $b,c$ as a horizontal and a vertical vector in the plane. As $c$ one takes either another horizontal or another vertical vector; non minimal matroid extensions take as $c$ a oblique vector in the plane or a vector outside the plane).

The group of automorphisms of the initial independence system contain the permutation that exchanges $b,c$ (and no other non-identity element). This exchanges the two minimal completion instead of being an automorphism for one of them, so the impossibility of "functoriality" is obtained.

Answer 2

An independence system has gone under a lot of other names. The most used of such is an abstract simplicial complex. As the name implies, these are very important in topology, and in combinatorics closely connected with topology. See

http://en.wikipedia.org/wiki/Abstract_simplicial_complex

Other names these have gone under include hereditary systems, down sets, ideals of sets, ...

Any simplicial complex $\Delta$ is the intersection of all matroids on the same vertex set containing $\Delta$ as a subcomplex. You can see this easily for example from the circuit definition of matroids -- a simplicial complex with a single minimal nonface ("circuit") is a matroid.

I don't know offhand of any canonical way to define a matroid from a simplicial complex. Simplicial complexes are considerably more general objects, so it seems a little unlikely that there would be one.

Answer 3

As the previous answers point out, there is no canonical or unique way to pass from an arbitrary abstract simplicial complex (a.k.a. independence system) to a matroid. One the other hand there is a lovely construction by Amini and Brändén for constructing a matroid from a pure simplicial complex (Theorem 6.3 in Non-representable hyperbolic matroids).

Fix an abstract simplicial complex $\Delta$ on a vertex set $E$. Then $\Delta$ is said to be pure if its inclusion-maximal sets all have the same size. (Note that if $\Delta$ is the independent sets of a matroid then it is pure, but that the converse doesn't hold in general). If $\Delta$ is pure of dimension $d-1$ then its facets are the (hyper)edges of a $d$-uniform hypergraph $G$. In this case make a new vertex set $F = E \cup E'$ consisting of two disjoint copies of $E$. Let $\mathcal{F}$ be the set of all subsets of size $2d$ in $F$ that are not of the form $e \cup e'$ for some edge in $e \in G$. Then $\mathcal{F}$ is the set of bases of a matroid.