general.hpp File Reference

Plans regarding matroids in Maxima/Lisp. More...

Go to the source code of this file.

Detailed Description

Plans regarding matroids in Maxima/Lisp.

Fundamental notions
  • A "matroid" is a special type of hypergraph.
  • A problem are the those many variations, i.e., whether to specify a matroid by the "independent subsets", by "circuits" etc.
  • Let "mtr" be the abbreviation for "matroid"; then perhaps we have "mtrx" for the variations:
    1. "ins" for independent subsets (a hypergraph [V,M] such that M is non-empty, hereditary (stable under subset-formation), and fulfils the augmentation property, i.e., for A, B in M with |A| < |B| there exists x in B - A with A + {x} in M; for implicitly given matroids, which could be infinite, we need further distinctions);
    2. "ds" for dependent subsets;
    3. "cr" for circuits;
    4. "bs" for bases;
    5. "rk" for a rank-function; here we don't have a hypergraph but a pair [V,f], where V is a set and f yields for every subset of V a natural number (with zero).
    6. "clos" for closure; perhaps we have a module in ComputerAlgebra/Sets, where we handle closure systems, i.e., pairs [X,f], X a set and f a map, which transforms subsets into subsets, in general.
  • The hypergraph-based notions should be given more "notational prominence" (than the others), perhaps always using 2-letters ?
  • Important to be complete and precise.
  • Important that all dual notions are easily at hand, perhaps the letter "d" is reserved to indicate "dual notions".
  • We also need to be compatible with oriented matroids; see ComputerAlgebra/Matroids/Lisp/OrientedMatroids/plans/general.hpp.
  • The direct definition is inefficient:
    1. The possibility of implicit representations of the base set is of importance especially for infinite matroids.
    2. And perhaps the existential quantifiers in the axioms can additionally be realised, e.g. for "_is" a function f(A,B) which yields x in B - A.
    3. In this way, through the different axiomatisations, many different functions arise, given directly or derived. One needs a system for that.
    4. Perhaps we use for example "isr", that is, "independent set realiser". One could also use "issf" ("sf" for "Skolem function").
    5. Perhaps important also the variation where e.g. f(A,B) is the set of *all* x in B - A s.t. A + x is independent.
    6. Importantly, also for the various set systems (independent sets, circuits, etc.) we can have explicit and implicit representations. One could use "imp" for "implicit", and "exp" for "explicit".
    7. Perhaps we make implicit representation of the set of independent subsets the default, while for the bases the explicit representation is the default.
  • Vector matroid M[A]:
    1. Given a combinatorial matrix A over a skew field, subsets of the column-set, or, alternatively, of the row-set, are independent iff they are linearly independent.
    2. With the Maxima function "rank" one can handle the field of reals or the field of rationals, while for other fields apparently no functions are provided, and so we need to provide generic functions ourselves.
    3. See "Missing functionality" in ComputerAlgebra/Algebra/Lisp/plans/FiniteFields.hpp.
  • Cycle matroid M(G):
    1. Given a general graph G, the sets of edges of cycles yield the set of circuits of a matroid on E(G).
    2. Here the check is easy: Compute the induced subgraph and check whether it is a cycle graph; this is done by cycle_gg_p and edge_induced_subgraph_gg.
Greedy algorithm
  • Given a hereditary hypergraph [V,E] with non-empty E, and a weight function w: V -> RR, the greedy algorithm determines a maximal element B of E as follows:
    1. B := {};
    2. if there is no x in V - B with B + {x} in E, return B;
    3. otherwise choose such x with w(x) maximal, set B := B + {x}, and repeat from the previous step.
  • The hereditarity condition exactly ensures that every B could be chosen.
  • [V,E] is a matroid if and only if the greedy algorithm yields for every w a maximal element of E which is also of maximal weight (amongst all maximal elements of E).
  • The two main variation seem to dependent on how to find x:
    1. Either one has to run through all of V - B,
    2. or a special function computes them.
  • So here for more efficient implementation a function f(I) would be needed, which for a given independent set I computes the set of all x in V - I s.t. I + {x} is still independent.
    1. For example for Kruskal's algorithm, f needed internal state, and would start with all edges possible, and with every edge added to B would remove all edges which now lead to cycles.
    2. How is Kruskal's algorithm doing that?
  • The greedy algorithm can find all bases of maximal weight; if x is always chosen randomly, do we then sample all bases fairly?

Definition in file general.hpp.