Google Summer of Code

[Stefan van Zwam]

Hi all,

Sage is applying to be a mentoring organization for the Google Summer of Code. Briefly, Google will pay students $5,000 to work on an open-source project during the summer. Last year we accepted a student to work on graph theory and matroid theory, but he bailed at the last moment. I hope to try again this year. We will need a description to go into Sage's project proposal. The prospective students will then need to flesh that out into a more concrete plan for the summer.

What needs to happen now is for potential mentors to step up (I will volunteer, maybe Rudi can join?), and for our section of the proposal to be written. Below is last year's proposal:

Matroid theory

Description	matroids are combinatorial abstractions of a number of mathematical objects, including graphs and matrices. Sage will soon have support for matroids, but lots of work remains to be done. Some projects with high priority are: Efficient routines for testing connectivity, and extending matroids while preserving connectivity Computing the automorphism group of a matroid More efficient minor testing Build a framework for collections of matroids. This includes database support (for inspiration, look at Sage's Graph Database).
Mentor	Stefan van Zwam Backup: Rob Beezer
Difficulty	Easy (programming), intermediate to hard (mathematics)
Skills	Python Background in combinatorics, linear algebra, ideally matroid theory.

I appreciate all help getting this thing done, because this and next week will be extremely busy for me.

--Stefan.

[Rudi Pendavingh]

Hi Stefan,

1) I can be mentor, but not (or only very lightly)  in the period from 5/7 to 17/8 -- and that is when the projects are supposed to end. But I can certainly instruct the programmer on the nature of a project before that period. If I can co-mentor, that should solve the problem.

2) I can think of three attractive projects:

a) Visualization of matroids of rank at most 4. No need for the student to have a deep knowledge of matroid theory here. A computer science student with some background in visualization could probably do a terrific job.

b) Testing if a matroid is binary, ternary, or quaternary. Takes a little bit of theory, but not much.

c) Isomorphism testing for binary matroids. I have several more tricks up my sleeve to further exploit Tutte invariants for this task. Appropriate for a student of mathematics.

*) I also like the connectivity project, and I think we should keep it. But here you really need someone who studies matroid theory, and they are perhaps hard to get.

*) Computing the automorphism group, in Sage, is really a matter of making the right translations. It is dead easy to do it poorly. The real work is in optimizing what you have for efficiency.

*) I think efficient minor testing for linear matroids (and testing for represented minors) is perhaps more interesting. I cannot think of a nice way to test for minors in a general matroid, but for linear matroids there are perhaps things to exploit.

Cheers,

Rudi

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