matroids axioms and independence system

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.

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.