Sage (not the accounting software, but sagemath.org) is accepted to Google Summer of Code 2012, and I will be one of many mentors.
Posts Tagged ‘teaching’
Sage (sagemath.org) at GSoC 2012
19 March, 2012Experimental Sage-based Mathematics course
7 August, 2011We are to embark upon teaching a 2nd year undergraduate course Experimental Mathematics, which will cover computer algebra basics, and refresh concepts from 1st year linear algebra, calculus, and combinatoris, with few more advanced things thrown in. The course will be based on Sage, with the actual software running on dedicated servers, and accessible via Sage web notebook interface (i.e. basically nothing but a web browser running on the student’s computer/laptop/ipad, etc).
Given the enrollment of about 120, this will be interesting…
PS. Most students did not appreciate the freedom given, and complained, complained, complained…
Is C++ the worst 1st programming language for maths majors?
7 May, 2010In our department we have a 1-semester course called “Introduction to scientific programming”, that is taught to the 1st year undergrads. It is C++-based. I am arguing for years that it is a real waste, and only good for getting people dazed and confused, and that instead something like Python should be used.
The choice of Python is basically due to it being interpreted, (largely) untyped, and higher level than C/C++.
(And last but not least, free, unlike Maple, Matlab, and Mathematica, which might be marginally more useful to a maths major).
Here is a ranking of programming languages in industry. Inevitably biased in some ways, I suppose it still demonstrates that claimed “superiority” of C++ is nowhere to be seen…
Bipartite matchings via linear programming
14 September, 2009An important tool for combinatorial optimisation problems, and graph problems among them, is linear programming, a method (and a problem) to find the optimum of a linear function on a polyhedron (i.e. on an intersection of half-spaces.) Often, such an intersection is bounded, and then one talks about a (convex) polytope rather than a polyhedron.
The optimum of a linear function on a polytope is always reached on a vertex, or, more generally, on a set of vertices of generating an optimal face. (A vertex is a point in that cannot be written as a nontrivial convex combination of two other points of )
Here we demonstrate a way to encode the problem of finding the size of a maximum matching (or, more generally, the maximum weight of a matching) in a bipartite graph as a linear programming problem.
As a warmup, we treat perfect matchings. Consider the vector of variables and the system of inequalities
Certainly, if is the characteristic vector of a perfect matching of i.e. is a 0-1 vector with 1s corresponding to the edges of it satisfies the system above. Thus maximizing the linear function on the polytope defined by gives an upper bound on the size of a maximum weight perfect matching in w.r.t. the edge weights
But in fact much more holds: namely, this bound is tight, as follows from the following theorem.
For a bipartite graph the vertices of the polytope defined by have 0-1 coordinates, and are in the one-to-one correspondence with the perfect matchings of
Proof. Let be a vertex of and be the support of i.e. Then does not contain a cycle. Indeed, a cycle in can be decomposed into the disjoint union of two (not necessarily perfect) matchings, say and as is bipartite and so each cycle in is even. Observe that for any
Thus there exists such that and so contradicting the assumption that is a vertex (and so it cannot be a convex combination of two points in ).
Thus is a forest. Let be a leaf of a subtree of Then implies that Therefore any connected component of is an edge, and so is a matching. It is a perfect matching by QED.
By this theorem, the maximum of on is reached on a perfect matching Another almost immediate corollary is the following well-known result on doubly stochastic matrices (an nonnegative real matrix is called doubly stochastic if its row and column sums are equal to 1.)
A doubly stochastic matrix is a convex combination of permutation matrices.
Indeed, -permutation matrices (the 0-1 doubly stochastic matrices) are in one-to-one correspondence to the perfect matchings of (the characteristic vector of such a matching can be viewed as an matrix, with rows corresponding to one part of the graph, and columns to the other) and so the doubly stochastic matrices are exactly the points of the perfect matching polytope of that has, by our theorem, perfect matchings as vertices (and so any point in it is a convex combination of perfect matchings).
Excercise. Formulate an analogy of system for matchings (not necessarily perfect) in bipartite graphs, and prove the corresponding result for vertices of the polytope in question. Using it, formulate the linear programming problem with optimal value being the size of maximum matching.
Excercise. Show that these constructions fail for non-bipartite graphs.
Bipartite matchings and SDRs
14 September, 2009Matchings in bipartite graphs and systems of distinct representatives (SDRs) of systems of subsets are closely related. More precisely, let for a finite set. We can construct a bipartite graph where
An SDR of is such that for all and for all In particular contains exactly one element for each
Then is a matching of saturating the part In particular, it is a maximum matching.
Conversely, a matching of saturating gives rise to an SDR for
An obvious necessary condition for existing of an SDR for
is the following Hall’s condition:
In view of this, Hall’s Theorem for matchings is equivalent to the following
An SDR for exists iff it satisfies Hall’s condition.
To see that Hall’s condition is sufficient, we proceed by induction on For the claim is obvious. Assume that it is true for all collections of less than sets. We now establish that it holds for -set collections, too.
If then we take any and set for some Now by induction there is an SDR for Then is an SDR for
In the remaining case there exists such that By induction, there is an SDR for
Let Then for otherwise contradicting Hall’s condition. Now we can take an SDR for and observe that is an SDR for
5-list-colouring of planar graphs
8 September, 2009A list-colouring of a graph with a colour list for is a proper colouring of by elements of so that the adjacent vertices are coloured in different colours and the colour for is in In particular, when all the s are equal to each other we have a classic graph colouring.
is called -choosable, or list-colourable if it is list-colourable for any satisfying for all The minimal for which is is choosable is called the list chromatic number of and denoted by Certainly,
It is not hard to construct examples when e.g. take and consider where vertices in the size two part of get colour sets .
Using the fact that each planar graph has a vertex of degree at most 5, as can be easily established using the Euler formula, one can prove that each planar graph is 6-choosable (employ induction by removing a minimal degree vertex).
It is less easy to show that
any planar graph is 5-choosable.
This was established in 1994 by Thomassen.
In fact cannot be improved — there are examples of planar for which The smallest known (in 2003) example has 63 vertices.
The classical analogy of this, the Heawood theorem that says that each planar graph is 5-colourable, is known since 1890, and the 4-colourability is a recent and quite difficult result by Appel and Haken.
To show the 5-choosability, one first observes that it suffices to prove it for the planar graphs for which every face, except possibly the exterior face of the plane embedding, is a triangle. We call such graphs almost triangulated. Then, one proceeds by induction on Assume that we know that for any almost triangulated planar with exterior face and such that for all resp. for all we can extend a proper -list-colouring of an edge on to a full proper -list-colouring (as is obviously true provided giving us a basis of induction).
Let us now show this for with Let be an edge of that we colour using and
If has a chord, i.e. there is an edge that joins two non-adjacent vertices of the cycle induced on (and so is not cutting through the fact bounded by the cycle on ), we spilt into two planar parts and so that and have in common. W.l.o.g. by induction, we can extend this colouring to a list-colouring of This colouring will fix a proper list-colouring of the edge that is on the exterior face of Again, by induction, we can extend this colouring of to a list-colouring of Combining and we obtain a list-colouring of as required.
It remains to consider the case when does not have a chord.
Then let be the vertex adjacent to Take any two colours in (this is possible as ) and remove from for all Then remove and all the edges on it from We obtain a planar graph with one vertex less, and with the valid exterior face conditions. By induction, we can extend the colouring of to a list-colouring of It remains to see that can be properly coloured, too. Indeed, we can colour it with either or depending on the colour of the neighbour of on distinct from Q.E.D.
we had a midterm last week…
10 March, 2009
more animals