## Posts Tagged ‘maths’

### Sage (sagemath.org) at GSoC 2012

19 March, 2012

Sage (not the accounting software, but sagemath.org) is accepted to Google Summer of Code 2012, and I will be one of many mentors.

### Installing CPLEX 12.2 on Debian amd64 and MacOSX 10.6 (64-bit)

24 September, 2010

IBM now gives CPLEX to academics for free; as I am computing LP bounds for quantum codes, I got myself one. However, it refused to install on my amd64 Debian system, saying

"libgcc_s.so.1 must be installed for pthread_cancel to work".

After much googling, it turned out that the installer is a 32-bit program, that needs the right 32-bit libgcc_s.so to work.
To get this on Debian (squeeze), I just did
$apt-get install ia32-libs Then $ LD_LIBRARY_PATH=/usr/lib32; sh cplex_studio122.acad.linux-x86.bin
worked as it should.

The installation goes smoothly on a 64-bit MacOSX 10.6. But running is not: one has problems when doing
 >>> import cplex ... from cplex._internal.py1013_cplex122 import * ImportError: dlopen(/Library/Python/2.6/site-packages/cplex/_internal/py1013_cplex122.so, 2): no suitable image found. Did find: /Library/Python/2.6/site-packages/cplex/_internal/py1013_cplex122.so: mach-o, but wrong architecture 

One can make it work on by setting
\$ export VERSIONER_PYTHON_PREFER_32_BIT=yes
before starting the Python session (as IBM/CPLEX Support kindly told me; they promised a fix in an upgrade, too).

### Is C++ the worst 1st programming language for maths majors?

7 May, 2010

In 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…

### Hungarian algorithm, take 1

23 September, 2009

Hungarian algorithm is an efficient procedure to find a maximum weight matching in a bipartite graph $\Gamma=(V_1\cup V_2,E)$ with parts $V_1$ and $V_2$ and a weight function $w:E\to\mathbb{R}_+.$ Usually it is described in terms of potential functions on $V=V_1\cup V_2,$ and looks quite mysterious, as it hides the origin of the procedure, that is a variation of the augmenting path method for finding a maximum (unweighted) matching in $\Gamma.$ Here we describe this point of view.

Let $M$ be a matching of maximum weight $w(M)$ among all matchings of size $|M|.$ If $M$ is a maximum (unweighted) matching then we are done.

Otherwise, we construct a bipartite digraph $D=(V,A)$ by orienting all the edges in $M$ from $V_2$ to $V_1,$ and the remaining edges $E\setminus M$ in the opposite direction. We also construct the length function $\ell: A\to\mathbb{R}$ by setting $\ell(a)=w(a)$ for all $a\in M,$ and $\ell(a)=-w(a)$ for all $a\in A\setminus M.$ Observe that there no negative length (directed) cycles in $D$. Indeed, any directed cycle $C$ in $D$ contains equally many edges in $C\cap M$ from $M$ and in $C\setminus M.$ Note that $\ell(C)<0$ would mean that $w(C\cap M)< w(C\setminus M),$ and so $w(M)$ is not maximum among all matchings of size $|M|,$ as $w(C\triangle M)> w(M),$ whereas $|C\triangle M|=|M|.$

Let $V_1^M$ and $V_2^M$ be subsets of $V_1,$ resp. $V_2$ that are unsaturated by $M.$ We find (say, using the Bellman-Ford algorithm) a minimum length directed path $P$ between $V_1^M$ and $V_2^M.$ By construction of $D,$ $P$ is an augmenting path for $M.$ So $M'=M\triangle P$ is a matching satisfying $|M'|=|M|+1.$

Claim: $w(M')$ is maximum among all matchings of size $|M'|.$

We’ll prove this claim below. For now, we remark that it is obvious that this procedure, repeated with $M'$ taking place of $M,$ will find matchings of maximum weight among all matchings of size $1,2,3,\dots$ In the end it remains to select among these at most $\min(|V_1|,|V_2|)$ matchings one with maximum weight.

Now let us prove the claim. It certainly holds for $|M'|=1,$ as the procedure will select a maximum weight edge in $E$ and $M'$ will consist of this edge. So we can assume $|M'|\geq 2.$ Let $N$ be a matching of size $|M'|,$ and of maximum weight. We need to show that $w(N)\leq w(M').$ As $|N|=|M|+1,$ in the subgraph $N\cup M$ there
exists a connected component $Q$ that is a $M-$augmenting path $Q.$
But $P$ is a shortest $M-$augmenting path, so $\ell(Q)\geq\ell(P).$
On the other hand, $N\triangle Q$ is a matching of size $|M|,$ and so $w(N\triangle Q)\leq w(M),$ by induction. Now $w(N)=w(N\triangle Q)-\ell(Q)\leq w(M)-\ell(Q)\leq w(M)-\ell(P)=w(M'),$ as claimed. QED.

As described, we need to do less that $n=|V|$ loops of this procedure. In each loop, the Bellman-Ford dominates the complexity, so in total we need $O(n^2|E|)$ operations. In fact, we can stop as soon as we reached the situation when $w(M')\leq w(M).$

Let a matching $M$ have maximum $w(M)$ among matchings of size $|M|,$ and any matching $M'$ of size $|M'|=|M|+1$ satisfy $w(M')\leq w(M).$ Then $w(N)\leq w(M)$ for any matching $N$ of size bigger than $|M|.$

Proof. Suppose $N$ be a matching contradicting the claim, minimal w.r.t. $|N\triangle M|.$ Let $D$ be the digraph constructed from $\Gamma,$ $w,$ and $M$ as above. The connected components of $|N\triangle M|$ induce oriented cycles and directed paths on $D.$ Each such component will have a nonnegative total length, as neither there can be a negative length cycle in $D$ (see above) nor can there be a negative length $M$-augmenting path (otherwise we can construct $M'$). But this implies that $w(M)\geq w(N),$ contradiction. QED.

In particular, the complexity above can be improved to $O(n|M||E|).$

### Bipartite matchings via linear programming

14 September, 2009

An 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 $P$ is always reached on a vertex, or, more generally, on a set of vertices of $P$ generating an optimal face. (A vertex is a point in $P$ that cannot be written as a nontrivial convex combination of two other points of $P.$)

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 $\Gamma=(V,E)$ as a linear programming problem.

As a warmup, we treat perfect matchings. Consider the vector of $|E|$ variables $x=(x_{e_1},x_{e_2}...),$ and the system of inequalities

$x_e\geq 0,\ e\in E,\quad \sum_{v\in e\in E} x_e=1,\ v\in V,\qquad (*)$

Certainly, if $x=x_M$ is the characteristic vector of a perfect matching $M$ of $\Gamma,$ i.e. $x$ is a 0-1 vector with 1s corresponding to the edges of $M,$ it satisfies the system $(*)$ above. Thus maximizing the linear function $\sum_{e\in E} w_e x_e$ on the polytope defined by $(*)$ gives an upper bound on the size of a maximum weight perfect matching in $\Gamma$ w.r.t. the edge weights $w_e, e\in E.$
But in fact much more holds: namely, this bound is tight, as follows from the following theorem.

For a bipartite graph $\Gamma,$ the vertices of the polytope $P$ defined by $(*)$ have 0-1 coordinates, and are in the one-to-one correspondence with the perfect matchings of $\Gamma.$

Proof. Let $x$ be a vertex of $P,$ and $X$ be the support of $x,$ i.e. $X=\{e\in E\mid x_e> 0\}.$ Then $X$ does not contain a cycle. Indeed, a cycle in $X$ can be decomposed into the disjoint union of two (not necessarily perfect) matchings, say $M$ and $N,$ as $\Gamma$ is bipartite and so each cycle in $\Gamma$ is even. Observe that $\sum_{v\in e\in E} ((x_M)_e-(x_N)_e)=0$ for any $v\in V.$
Thus there exists $\epsilon>0$ such that $x\pm\epsilon(x_M-x_N)\in P,$ and so $2x=(x+\epsilon(x_M-x_N))+(x-\epsilon(x_M-x_N))),$ contradicting the assumption that $x$ is a vertex (and so it cannot be a convex combination of two points in $P$).

Thus $X$ is a forest. Let $e\in X$ be a leaf of a subtree of $X.$ Then $(*)$ implies that $x_e=1.$ Therefore any connected component of $X$ is an edge, and so $X$ is a matching. It is a perfect matching by $(*).$ QED.

By this theorem, the maximum of $\sum_{e\in E} w_e x_e$ on $P$ is reached on a perfect matching $x=x_M.$ Another almost immediate corollary is the following well-known result on doubly stochastic matrices (an $n\times n$ 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, $n\times n$-permutation matrices (the 0-1 doubly stochastic matrices) are in one-to-one correspondence to the perfect matchings of $K_{n,n},$ (the characteristic vector of such a matching can be viewed as an $n\times n$ 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 $K_{n,n},$ 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.

### 5-list-colouring of planar graphs

8 September, 2009

A $\mathcal{C}-$list-colouring of a graph $\Gamma=(V,E)$ with a colour list $\mathcal{C}=\{C(v_1),\dots,C(v_n)\},$ for $V=\{v_1,\dots,v_n\},$ is a proper colouring of $V$ by elements of $\cup_j C(v_j)$ so that the adjacent vertices $u,v$ are coloured in different colours and the colour for $v\in V$ is in $C(v).$ In particular, when all the $C(v)'$s are equal to each other we have a classic graph colouring.

$\Gamma$ is called $k$-choosable, or $k-$list-colourable if it is $\mathcal{C}-$list-colourable for any $\mathcal{C}$ satisfying $|C(v)|\geq k$ for all $v\in V.$ The minimal $k$ for which is $\Gamma$ is $k-$choosable is called the list chromatic number of $\Gamma$ and denoted by $\chi_\ell(\Gamma).$ Certainly, $\chi(\Gamma)\leq \chi_\ell(\Gamma).$
It is not hard to construct examples when $\chi(\Gamma)< \chi_\ell(\Gamma),$ e.g. take $\Gamma=K_{2,4}$ and consider $\mathcal{C}=\{\{1,2\},\{3,4\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\},$ where vertices $v_1,v_2$ in the size two part of $\Gamma$ get colour sets $C(v_1)=\{1,2\}, C(v_2)=\{3,4\}$.

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 $\Gamma$ is 5-choosable.

This was established in 1994 by Thomassen.
In fact $\chi_\ell(\Gamma)=5$ cannot be improved — there are examples of planar $\Gamma$ for which $\chi_\ell(\Gamma)=5.$ 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 $|V|.$ Assume that we know that for any almost triangulated planar $\Gamma$ with $|V\Gamma|\leq n,$ exterior face $B,$ and $\mathcal{C}$ such that $|C(v)|\geq 3$ for all $v \in B,$ resp. $|C(v)|\geq 5$ for all $v\in V\setminus B,$ we can extend a proper $\mathcal{C}$-list-colouring of an edge on $B$ to a full proper $\mathcal{C}$-list-colouring (as is obviously true provided $|V|\leq 3,$ giving us a basis of induction).

Let us now show this for $\Gamma$ with $|V\Gamma|=n+1.$ Let $(x,y)$ be an edge of $B$ that we colour using $\alpha\in C(x)$ and $\beta\in C(y)\setminus\{\alpha\}.$
If $B$ has a chord, i.e. there is an edge $(u,v)$ that joins two non-adjacent vertices of the cycle induced on $B$ (and so $(u,v)$ is not cutting through the fact bounded by the cycle on $B$), we spilt $\Gamma$ into two planar parts $\Gamma_1$ and $\Gamma_2,$ so that $\Gamma_1$ and $\Gamma_2$ have $(u,v)$ in common. W.l.o.g. $(x,y)\in E\Gamma_1;$ by induction, we can extend this colouring to a $\mathcal{C}-$list-colouring $\mathcal{A}_1$ of $\Gamma_1.$ This colouring will fix a proper $\mathcal{C}-$list-colouring of the edge $(u,v),$ that is on the exterior face of $\Gamma_2.$ Again, by induction, we can extend this colouring of $(u,v)$ to a $\mathcal{C}-$list-colouring $\mathcal{A}_2$ of $\Gamma_2.$ Combining $\mathcal{A}_1$ and $\mathcal{A}_2,$ we obtain a $\mathcal{C}-$list-colouring of $\Gamma,$ as required.

It remains to consider the case when $B$ does not have a chord.
Then let $z\in B\setminus\{x,y\}$ be the vertex adjacent to $x.$ Take any two colours $\delta,\mu$ in $C(z)\setminus\{\alpha\}$ (this is possible as $|C(z)|\geq 3$) and remove $\delta,\mu$ from $C(t)$ for all $t\in\Gamma(z)\setminus B.$ Then remove $z$ and all the edges on it from $\Gamma.$ We obtain a planar graph $\Gamma'$ with one vertex less, and with the valid exterior face conditions. By induction, we can extend the colouring of $(x,y)$ to a $\mathcal{C}-$list-colouring of $\Gamma'.$ It remains to see that $z$ can be properly coloured, too. Indeed, we can colour it with either $\delta$ or $\mu,$ depending on the colour of the neighbour of $z$ on $B$ distinct from $x.$ Q.E.D.

### a subgeometry of D_3-dual polar space

29 May, 2009

In 1991 I provided to Andries Brouwer more examples of distance-regular graphs that were not known at the time the book “Distance-regular graphs” by Andries, A.M.Cohen, and A.Neumaier, that he included into “Additions and corrections”. Recently I was asked for more details on these. So I started to recall what that was all about (I drifted quite far from that area of research since then, I must say)…

D3-dual polar space is a bipartite graph $\Gamma=(V,E)$ that satisfies the following properties:

• each 2-path lies in a unique complete bipartite subgraph $Q$ with parts of size $\geq 3;$
• for any vertex $v\in V$ the edges $(v,u)\in E$ and the subgraphs $Q\ni v$ form a projective plane $\Pi_v,$ with respect to inclusion.

So from the point of view of Tits’ “local” approach to buildings we talk about a “geometry with diagram” $\circ==\circ--\circ,$ where $\circ==\circ$ stands for a generalised 4-gon (and indeed complete bipartite graph is a trivial example of such a thing), and $\circ--\circ$ stands for a generalised 3-gon, i.e., a projective plane.

To construct a typical example, let us consider the case of the projective planes $\Pi_v$ being of order $q=3.$ Then we have a distance-regular graph of diameter 3, with distribution diagram around a vertex as follows:
[1]131[13]124[39]913[27]
So each vertex $v$ has 13 neighbours, 39 vertices at distance 2, and 27 at distance 3; each neighbour of $v$ has 12 neighbours at distance 2 from $v,$ each distance 2 vertex has 4 mutual neighbours with $v,$ and 9 neighbours at distance 3 from $v.$

Such a graph is unique: this is so for each $q$ a prime power, in fact, there is 1-to-1 correspondence between such graphs and 3-dimensional projective spaces: take as points (resp. planes) of the space parts of the bipartition, with incidence being the adjacency in $\Gamma,$ and subgraphs $Q$ as lines, with adjacency between lines and points (resp. planes) being inclusion.
And $k$-dimensional finite projective spaces, for $k\geq 3,$ are all coming from the natural construction from the 4-dimensional vector space over a Galois field.

Another natural construction of $\Gamma$ comes from a non-degenerate 6-variate quadratic form, over $\mathbb{F}_q,$ of maximal Witt index (i.e. a form that cannot be rewritten as a form with lesser number of variables using a nondeg. linear transformation, and such that there are totally isotropic subspaces of dimension 3, the maximal possible in fact). Recall that a subspace $U$ is called totally isotropic w.r.t. to a form $\langle , \rangle$ if $\langle s , t \rangle=0$ for all $s,t\in U.$
Then the vertices of $\Gamma$ are the maximal totally isotropic subspaces, with adjacency being the maximality of the intersection dimension (i.e. two vertices are adjacent iff the corresponding 3-spaces intersect in a 2-dimensional subspace).

Example. For $q=3$ one can take $\langle X,X\rangle=X_1 X_2-X_3^2-X_4^2-X_5^2-X_6^2,$ and a maximal totally isotropic subspace with a basis
$\{(1,0,\dots,0), (0,0,0,1,1,1), (0,0,1,1,-1,0)\}.$
The advantage of this construction is that it allows to describe dual polar graphs $D_k$ for $k\geq 4$ as well. (Take $2k$-variate nondeg. form of maximal Witt index equal to $k$, etc.)

We are interested in constructing a subgraph $\Delta$ of $\Gamma$ that behaves
like $\Gamma$ when we look at the neighbours of $v,$ with the difference that edges on $v$ and the subgraphs $Q$ on $v$ now form an affine plane, not a projective one. So $Q\cap\Delta \cong K_{q,q},$ while $Q\cong K_{q+1,q+1}.$ In order to do so, we pick up an edge $(s,t)\in E\Gamma,$ and remove from the latter all the vertices adjacent to either $s$ or $t.$ The resulting graph is exactly $\Delta$ that we want!
In terms of maximal totally isotropic subspaces, the vertices of $\Delta$ are these ones that have 0 intersection with the 2-dimensional subspace corresponding to the intersection of the 3-dimensional subspaces corresponding to $s$ and $t.$ We have a distance-regular graph of diameter 4, with distribution diagram (for $q=3$) around a vertex as follows:
[1]91[9]83[24]68[18]19[2]
It is a $q-$fold antipodal cover of $K_{q^2,q^2}$, i.e. the vertices are partitioned into sets of size $q$ such that pairwise distances between vertices in each of them are maximal, i.e. 4, and there is a naturally defined structure of complete bipartite graphs on them.