Matroid Theory

A very brief description from the page at the following link:

Matroids are a generalization of several combinatorial objects, among them graphs and matrices. They can represent more mathematical objects than graphs or matrices. In fact they can represent any mathematical object. The word matroid was coined by Whitney in 1935 in his landmark paper "On the abstract properties of linear dependence". In defining a matroid Whitney tried to capture the fundamental properties of dependence that are common to graphs and matrices. Matroid theory provides a framework in which problems in combinatorial optimization, operations research and graph theory become simpler to understand.
Matroids consist of a ground set E and a set I of subsets of E (called "independent sets") such that:

The last rule implies that you can find a "walk" from any subset in I to any other, replacing one element at a time.
I'm having a little trouble with the last condition in that definition. It lacks quantifiers -- both the element being removed and its replacement need to be quantified as either "for every" or "there exists". Without this info, the definition is not well-formed.

My initial post pointed out that the definition could have one of four meanings. A responder (PhlIp?) removed all but this one:

And added this explanation:

Right. The meaning is this: Group all subsets S of I into sets of the same cardinality (number of elements). For each group, you can "walk" the group by starting at one S, replace one element, get another element of the group, and keep going in a unique path back to the starting S.

BTW I (PhlIp) am only qualified to abuse math to support baloney, so get a second opinion.

This second opinion says the above definition is wrong (consider S = {}). A correct definition (see is:

(Note that this is the same as "Given any two independent sets of different sizes, there's an element of the larger one that you can add to the smaller one while keeping it independent" as stated below.)

Actually, get more than two opinions.

Actually, get a set of opinions such that changing an assertion in any one opinion yields another opinion in the set... ;-)

I continue (after acknowledging the humour :-)

The explanation you've given explains the intent of the definition. I shall have to spend a few minutes sometime playing with the definition to see if it yields the intended property. -- ScottCooper
Further, all the other hooey does not mean "you can fit every graph or independent vector sets in projective spaces or a matrix into a matroid". It just means aspects of those things can often be represented as aspects of matroids.

There are those who claim that a RelationalDatabase is a matroid.
I don't understand why the last axiom, as stated, implies that you can walk from any subset in I to any other. Suppose E = {1,2,3,4,5,6} and I consists of {1,2},{1,3},{4,5},{4,6} and all subsets of those sets. Every set in I can have one of its elements replaced to produce a new element of I; but you can't walk from 12 to 45 changing one element at a time.

Your set I is incorrect: {1,2} is in I, but {1,4} is not in I, so I does not satisfy axiom 3.

It seems that this confusion stems from the ambiguity in axiom 3. -- ScottCooper

It would appear that I is always either the empty set or the power set of E. I challenge anyone to demonstrate otherwise. -- IanKjos

Here you go: Let E = {a,b,c}, and I = {{},{a},{b},{c}}.

I want to dig up some of the LatticeTheory? I studied. I see that a matroid can be described in terms of the lattice of subsets of the ground set (E).
I've seen the last axiom stated as "Given any two independent sets of different sizes, there's an element of the larger one that you can add to the smaller one while keeping it independent". That does have the "walk from anywhere to anywhere else" property. But maybe I've misunderstood the intent of the last axiom as stated above?
Okay, now would anyone care to contribute an explanation of what a matroid design is?

Definition --
Introductory Books List CategoryMath

View edit of September 25, 2011 or FindPage with title or text search