Re: [Axiom-developer] Some links on Matroids

[Bertfried Fauser]

On Sun, 4 Jan 2004, David MENTRE wrote:


Dear David!


        the idea with the matroid was a far reaching one, not assumed to
be practical at the very moment. I can however explain what in my mind is
behind this idea.

* In the 30ies (if I am right) Hassler Whithney started to think about
dependency of mathematical terms. Think of:
-  Linear dependence. This needs a module and a ring the module is build
  over.  A dependency is a *linear* relation between elements of the the
  module. This is the dependency attached to linear algebra. Its too
  weak to describe more sublte dependencies.
- Algebraic dependence. Think of a cyclic group (or modulo arithmetik)
  where relations like x^n=1 emerge. No scalars involved here. Similar
  problems occurer in Hilberts syzygie theory, where one has an
  *algebra of dependencies*.
Whitney set out to distill from these type of problems the core of the
term *dependent* and coined for that the matriod definition.

* A most perplexing feature of matroids is that they are *cryptomorphic*.
That is, matriods can be defined in quite different terms and there are
proofs that these definitions are equivalent. Eg. matroids can be defined
on graphs or on linear spaces. It shows up, that theorems easyly proved
inthe graph picture might be quite hard theorems in the linear space
picture and vice versa. This is nicely explained in a book by Peter
Laeuchli, ETH Zurich (can`t remember the title, something like
introduction to matroids for computer scientists)
        Hence there is only the abstract notion of matroid and various
*presentations* which might be more or less useful.` in a given context.

* If you are familira with incidence geometries, you may address a matriod
as a generalization of such a geometry. This is the point where I think
matroids could help to handle the algebra depencency problem.

Let us think of the following setting. We have atributes, totally ordered
by complexity (say most complex is the code itself, and least complex is a
user help page describing usage or even just examples). We may consider
this complexity as a sort of dimension or *grading* and attach to each
such concept a sort of hypervolume. Code is one dimesnional, examples are
high dimesnional.
        A dependency of two objects may then be described via an inclusion
operation (incidence relation). If a piece of code belongs to a domain,
category or user example, then there is a dependency. One might even think
of computing the dimension of the common part to give a measure how
dependent two concepts are.
        This type of dependency is nonlinear in general.



I am not yet sure how, but expect the following to be possible: Matriod
techniques should help to formalize and handle dependency relations in
such a high dimensional object. (its not only a graph, since you have not
only edges and vertices, but also volumes, hypervolumes etc.)
        Helpful in this quest is the exchange property of matroids. Every
matroid has a set of bases, say B={b_1,b_2,...} where b_i are bases. You
might select two bases, say b_1 and b_2 and wish to delete one basis
element from b_1, say x, then there is always one element z in b_2 such
that b_1\x \/ {z}  (\/ means union here) is again a basis. Such algorithms
can be used to modify dependencies into a wishful way.

What would be needed to implement such a matroid based nonsense. The hard
thing is that one would have to describe somehow all possible dependencies
(alternatively all independent sets) of the whole set under consideration
(might be derivable from Tims index charts). Then it should be possible to
ask questions like
  what ring has attribute X do not use "has commutative"
to retrieve information about the category ring having attribute X but
eliminate (if possible) the depencency on the attribut "has commutative"

To be frank, I cannot implement such a thing in software!

WARNING:
* There are matroids which cannot be described as vectorsapce matroid
* Matroids which can be described by vectors, might need a quite peculiar
  ring of scalars, say Z_2 or even more awkward

hope this explains my thinking a little bit,
cheers
BF.

% |   | PD Dr Bertfried Fauser    Fachbereich Physik    Fach M 678  |
%  \ /  Universit"at Konstanz     78457 Konstanz        Germany     |
% (mul) Phone : +49 7531 693491   FAX : +49 7531 88-4864 or 4266 (comul)
%   |   E-mail: address@hidden                   / \
%   |   URL   : http://clifford.physik.uni-konstanz.de/~fauser    |   |