Fun with sage-matroid

[Thierry]

Dear sage-matroiders,

i am in charge to organize some sage sessions during a research school
in theoretical computer science soon http://ejcim2013.univ-perp.fr

One of the lectures of the school deals with matroids (both non-oriented
and oriented) and i would like to do some sage practice about matroids,
using your package.

Unfortunately, i am not specialist of matroids and do not know what
funny worksheets about matroids i could write, in order to help
participants to get intuition about matroids and enjoy the session (e.g.
nice illustration of an abstract result, surprising evidence, how
matroids can be used to attack some apparently unrelated problem,
problems producing nice pictures, "real-life" examples of matroids,
...).

Do you have any idea/suggestion about that ?

Best regards,
Thierry

[Stefan van Zwam]

Dear Thierry,

What to illustrate depends a lot on what the lecturer covers.

To see what kinds of data can produce matroids, look at the Matroid function. For instance, this creates a matroid out of a graph:

G = graphs.PetersenGraph()
M = Matroid(G)

Unfortunately we don't have any code in place yet to display matroids, but other parts of Sage can. This constructs and displays the Lattice of Flats of matroid M:

M = matroids.named_matroids.Fano()
F = []
for i in range(M.rank()+1):
F.extend([frozenset(X) for X in M.flats(i)])
P = Poset((F, lambda x, y: x <= y))
P.show()

The following code (which we should definitely package in a more user-friendly way) generates all nonisomorphic matroids up to N elements and rank R:

class MatroidSet():
def __init__(self, MM=None):
self._R={}
if MM is not None:
self.add(MM)

def add(self, MM):
for M in MM:
q=M.weak_invariant()
if q in self._R:
found=False
for N in self._R[q]:
if M._is_isomorphic(N):
found=True
break
if not found:
self._R[q].append(M)
else:
self._R[q]=[M]

def __len__(self):
return sum([len(v) for v in self._R.values()])

def __iter__(self):
return self.list().__iter__()

def list(self):
return flatten(self._R.values())

# BasisMatroid generation
def all_matroids(N,R=None):
if R is None:
R=N
MM={}
MM[0,0]=MatroidSet([BasisMatroid()])
print [1]
for n in xrange(N):
MM[0,n+1]=MatroidSet()
for r in xrange(min(R,n)+1):
for M in MM[r,n-r].list():
MM[r,n-r+1].add(MatroidExtensions(M,n,orderly=True))
if r<R:
MM[r+1,n-r]=MatroidSet([M._with_coloop(n) for M in MM[r,n-r].list()])
print [len(MM[r,n+1-r]) for r in xrange(min(R,n+1)+1)]
return MM

The first computer code to generate matroids was done by Crapo, Blackburn, Rota in the '70s. They found all nonisomorphic matroids up to 8 elements. Sage does that in under 5 seconds:

%time
S = all_matroids(8)

Note that 9 elements is feasible, but will keep you waiting for some 15 minutes (if I recall correctly).

For linear codes, the Weight Enumerator is an evaluation of the Tutte Polynomial of the corresponding matroid. Example:

C = HammingCode(3, GF(3))
x, y = var('x,y')
p = C.weight_enumerator('xy')

And the corresponding matroid and Tutte polynomial:

M = matroids.PG(2,3).dual()
t = M.tutte_polynomial(x,y)
u = t.substitute({x: 3*y/(x-y)+1, y: (x-y)/y+1}) * y^3 * (x-y)^10
q = u.full_simplify()

Now if you compute

p - q

you get 0.

One last example: showing that R10 is a splitter for the regular matroids.

R10 = matroids.named_matroids.R10()
print R10.linear_extensions(simple=True)
print R10.linear_coextensions(cosimple=True)

Both lists will be empty, i.e. R10 has no simple single-element extensions that are regular (and therefore no 3-connected single-element extensions).

Unfortunately we have not worked on any oriented matroid stuff, and in my experience the questions that matroid theorists ask are completely different from those asked by oriented matroid theorists (e.g. in the book on oriented matroids, the word "connectivity" doesn't occur in the index).

I hope this helps! Feel free to ask for more examples.

Cheers,

Stefan.

> --
>
> ---
> You received this message because you are subscribed to the Google Groups "sage-matroid" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Thierry]

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

[Stefan van Zwam]

Dear Thierry,

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

There is, using matroid union. Unfortunately we haven't implemented matroid union yet, so I had to improvise using matroid intersection. I've basically implemented matroid union of 2 matroids (using pretty slow ad-hoc code), and use it to find your two bases. See the attached Sage worksheet (it also has a reference).

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

Plenty! Some small examples:

# Non-representable to representable:
sage: M = matroids.named_matroids.Vamos()
sage: N = M.contract('a').delete('b')
sage: N.is_isomorphic(matroids.Uniform(3,6))
True

# non-regular to regular:
sage: M = matroids.named_matroids.Fano()
sage: N = M.delete('g')
sage: N.is_isomorphic(matroids.Wheel(3))
True

# regular non-graphic to graphic
sage: M = matroids.named_matroids.R10()
sage: M.is_graphic()
False
sage: N = M.delete('a')
sage: N.is_graphic()
True
sage: N.is_isomorphic(Matroid(graphs.CompleteBipartiteGraph(3,3)))
True

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

Let's stick to graphs. Here are two nice ones.

Number of spanning trees:

sage: G = graphs.PetersenGraph()
sage: G.spanning_trees_count()
2000
sage: Matroid(G).tutte_polynomial(1,1)
2000

Chromatic polynomial (the formula is for connected graphs only):

sage: p = G.chromatic_polynomial()
sage: x = var('x')
sage: p = G.chromatic_polynomial()
sage: q = Matroid(G).tutte_polynomial(1-x, 0) * x * (-1)^(G.num_verts()-1)
sage: (p - q).expand()
0

> - rigity matroid
> - secret sharing

I don't know much about the rigidity matroid. Maybe Michael Welsh can weigh in on secret sharing?

Cheers,

Stefan.

[Michael Welsh]

On 4/04/2013, at 4:39 PM, Stefan van Zwam <stefan...@gmail.com> wrote:
>
> Maybe Michael Welsh can weigh in on secret sharing?

First, a good reference for secret-sharing matroids is Part 2 of my Masters: http://yomcat.geek.nz/maths/masters_final.pdf

Seymour's definition is the only one out there (it's slightly wrong in my thesis (and the original paper) -- you need to exclude the trivial case). As to computation using this, I did a little, but it's really ``hard''. You can show that a particular matroid is secret-sharing over a particular alphabet easily enough (assuming the alphabet is small), and the code for that isn't too hard to write. It'll be even easier with sage_matroid, because you have a rank function already.

The converse, showing that a matroid is not secret-sharing, is the hard part, because there's no bound on the alphabet size. IIRC, the handful of matroids that have been shown to be non-secret-sharing (such as the Vamos in Seymour's paper) have all used some trick, not at all related to anything computational.

Basically, the only thing I think is feasible is to show that a particular matrix is a secret-sharing matrix for a particular matroid. There are a couple of examples in my thesis, along with some constructions for making others.

I only looked at secret-sharing matroids from a matroid structure theory viewpoint. I know that there are people that look at it from an Information Theory viewpoint and have lots more results than I was able to get. Whether they're helpful for computational teaching or not is not something I know anything about.

HTH,
Michael