RE: [Axiom-developer] Some links on Matroids

[Page, Bill]

On Monday, January 05, 2004 5:31 AM Bertfried Fauser
[mailto:address@hidden wrote:
> ... 
> * 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 easily proved in the 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)

I haven't found any reference on the web to a book by
Peter Laeuchli about matroids. But I do know of some
lecture notes entitled:

  Combinatorics for Computer Scientists
  by Dany Breslauer and Devdatt P. Dubhashi. 

see

  http://www.brics.dk/LS/95/4/BRICS-LS-95-4.ps.gz

in

  http://www.brics.dk/LS/95/Abs/BRICS-LS-95-Abs/

also containing some other interesting lectures on
polymorphic type inference and category theory.

---------

Combinatorics for Computer Scientists contains useful
self-contained chapters on both graph theory and on
algorithms involving matroids. For matroids refer to
chapter 23, page 185.

>From this discuss it is quite clear, I think, how the
concept of matroid (Example 178), matroid bases and
the problem of finding a "maximal independent set of
minimum weight" (Theorem 195) relates to the issue
that Tim and I discussed much early of optimizing the
algebra "bootstrap" for building Axiom.

> ... 
> 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.)

I think, maybe, what Bertfried is saying is that the
graph matroid that we can construct from the usual
dependency (call) graph is not the most general matroid
possible and therefore the dependency graph does not
represent all of the types of dependencies in which
we may be interested - even though it is apparently
sufficient for the bootstrap problem.

>       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 dependency
> on the attribute "has commutative"
> 
> To be frank, I cannot implement such a thing in software!

Perhaps this might be possible using software such as

  http://www.mcs.vuw.ac.nz/research/macek/

"(MAroids Computed Efficiently Kit)

by Petr Hlineny

Overview
This project is a set of tools and routines for reasonably
efficient combinatorial computations with represent able
matroids, especially for matroid constructions and for
some structural tests. (If you do not know what a matroid
is, then this project is likely not for you.) The program
is intended both to help with everyday routines that a
matroid-researcher faces (almost) every day, and to allow
for long exhausted computations of matroid classes and
their properties. ..."

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

-------------

However, about all of this I remain rather sceptical.
It is not clear to me that this notion of dependency
is what is really important - at least in the context
of the algebra.

I think I would prefer a much more "structural" approach,
where perhaps more complex things (objects) are described
functorially in terms of other objects (or categories) and
operations on those objects that are simplier - often the
way things are actually defined in Axiom. Or by embedding
them into something more, or equally, complex but more well
understood by the reader - i.e. an example.

I think there needs to be some way for the user to
"navigate" over such functorial maps, maintaining on the
computer screen (or at least quickly retrievable) a summary
of the immediately relavant mappings as an aid to memory.

To the extent that Axiom is built in an "object oriented"
manner, this functorial approach should be extendable to
other parts of the system system - perhaps down to the
lisp level.

Cheers,
Bill Page.