Dear Stefan, dear all,
thanks for this reply. Here are some thoughts on my side (coming from
discussions and browsing the web).
- I am trying to let the students implement the shannon switching game (i
already wrote the interact, by not yet the winning strategies). If i
understand correctly, the strategy for the Join player is easy given a pair of
disjoint trees. This can easily be done in sage with
G.edge_disjoint_spanning_trees(2) Hence, if i want to find a strategy for the
Cut player, i should work in the dual matroid (implemented in sage-matroid),
and look for a pair of disjoint bases there. Unfortunately, this dual matroid
is not graphic, hence i have to implement this. Do you know an algorithm for
that ? Note that G.edge_disjoint_spanning_trees(2) is solved by integer linear
programming in sage (see
http://hal.archives-ouvertes.fr/inria-00504914/en for
explanations), is there such a formulation for general matroids ?
You can find a human vs human interact worksheet in attachment (in french).
Some other possibilities are listed below, but i do not have a concrete
idea of what kind of sage coding exercises i could do with them (i
recall that i am not a matroid specialist).
- starting from a non-representable matroid, apply some operations (minor,
delete,...) and become representable in some field, regular , graphic, ...
(if you have such an example).
- It seems that the Tutte polynomial allows to count quite a lot of things, as
the example you gave with HammingCode. Could you give more explanations about
the relation between those two objects ? Also, are there other examples of
specialisation of the Tutte polynomial that could fits with sage ?
- rigity matroid
- secret sharing
On 14/03/2013 17:29, Stefan van Zwam wrote:
> What to illustrate depends a lot on what the lecturer covers.
Here is a translation of the table of contents of the lecture.
Theory of matroids and oriented matroids
1 Introduction
2 Theory of matroids
2.1 Axiomatic
Independants, circuits, bases, rank, closure, greedy algorithm
2.2 Application to combinatorial optimization
Transversal matroid, assignation problem
2.3 Duality
graphic case
2.4 Direct sum and connectivity
2.5 Minors
2.6 Representable or vectorial matroids
2.7 Regular Matroids
2.8 Union of matroids
2.9 Tutte polynomial
General properties
Graphical case: chromatic polynomial and flow polynomial
Regular case: Ehrhart polynomial
Oriented case: acyclic and totally cyclic orientations
3 Theory of oriented matroids
3.1 Some common classes and properties
Graphs
Pseudolines or pseudocircles arrangements
Vector or affine points configurations
Some geometric properties coded by the oriented matroid of a point configuration
3.2 Oriented matroids: combinatorial definition
Axiomatic of signed parts
Duality
Axiomatic of bases and chirotopes
Important notions
3.3 Oriented matroids: topological definition
Pseudospheres arrangements
Faces of the arrangement, covectors of the oriented matroid
Regions, maximal covectors, acyclic reorientations
Duality
Real case: arrangement of hyperplanes
3.4 Remarkable links with linear programming
Linear programming in oriented matroids
Farkas lemma
> This constructs and displays the Lattice of Flats of matroid M:
> [...]
It is also possible to use this to illustrate Rota's conjecture
http://www.openproblemgarden.org/op/rotas_unimodal_conjecture
sage: points((i,len(M.flats(i))) for i in range(5))
Ciao,
Thierry