Matroid Theory

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

http://members.aol.com/matroids/

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 empty set is in I
Every proper subset of every set in I is also in I
For every subset in I you can replace one element with another selection from E and get a new subset which is also in I

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:

Given a set S which is a member of I, there exists an element e in S, such that for every element f which is a member of E but not a member of S, if you remove e from S and replace it with f, the resulting set is still a member of I.

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 http://www.ms.uky.edu/~pagano/Matr1.htm) is:

If X and Y are both in I, and |X| is larger than |Y|, then there is some element x of X\Y such that Y union {x} is also in I.

(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?

Introduction

Definition -- http://www.math.washington.edu/~billey/classes/582/bulletins/wilson.matroids.pdf

A matroid M = (E,H) consists of a non-empty finite set E, together with a non-empty collection H of subsets of E (called bases) satisfying the following properties:
- (Hi) No base property contains another base.
- (Bii) If B, and B2 are bases, and x is an element of B,, then there exists an element y of B2 with the property that (B, - ( x ) )u ( y ) is also a base.

Introductory Books List

http://mathoverflow.net/questions/67736/good-introductory-text-book-on-matroid-theory

CategoryMath