Tunisia

Tunisia has been in the news for the wrong reasons. I sincerely hope that the people of this beautiful and hospitable country are not seriously harmed by the recent terrorist outrages.

The best I can do to show my solidarity is to post a few pictures I took at a conference in Mahdia I attended in 2008. The acronym of the conference was ROGICS; I no longer remember what this stood for, but never mind. We were in a tourist hotel (out of high season), but there was a real town, which you could walk to from the hotel.

Mahdia

You can read more in my travel diary.

Posted in geography, history | Tagged , | Leave a comment

Congratulations

… to Robert Schumacher, who passed his PhD viva this week. He has some revisions to do after a well-earned holiday.

Flowers

And thanks for the flowers!

Posted in Uncategorized | Leave a comment

July

July

July’s picture shows two herons around the Elora Gorge in Ontario, Canada. The first was fishing in the Grand River where I walked with Ian Wanless last year, on the outing at the Chris Godsil conference in Waterloo; the second was in a café in Elora where we went for a coffee afterwards.

Posted in geography | Leave a comment

On foundations

Jack Edmonds stayed in my house for two and a half weeks, while giving his two courses on polyhedral combinatorics in London (I reported on the second one here).

Whenever we spend time together, we have a robust discussion about the foundations of mathematics, from which we both gain something. The picture below shows an earlier discussion in a Chinese restaurant after Jack spoke in the Combinatorics Study Group at Queen Mary. The picture was taken by Carrie Rutherford.

Peter Cameron and Jack Edmonds

I want to report on our discussion last week. I am aware of the risk of misrepresenting Jack’s views; but I will trust to our friendship and carry on anyway. But of course, what I say here is my own take on things.

Jack is scathing in his dismissal of ZFC (Zermelo–Fraenkel set theory with the Axiom of Choice) as a foundation for mathematics. In his view, the basic problem is the Power Set axiom, since it is not specified what a subset of a set is. It is true that many vagaries slip in through this open window; but varying some of the other axioms (e.g. by assuming Gödel’s axiom V=L, or by replacing the Axiom of Infinity with its negation) makes the power set axiom harmless. I think part of Jack’s objection is the non-effectiveness; even if we understand what the subsets of a set are, there is no efficient way to list them all.

I think he is fairly content with Peano’s axioms. But the problem really goes deeper. One of our discussions was about the commutative law for multiplication. I discussed this here. To summarise what I said: the commutative law is obvious to everyone who has thought about a rectangle of dots; proving it in PA is a nightmare, involving a double induction; proving it in ZFC is much closer to the intuitive argument, since there is a natural bijection between A×B and B×A (just turn around all the ordered pairs).

Jack’s view, as I understand it, is that the foundations of mathematics should be much closer to our psychological picture than it is at present. I will discuss a bit what he thinks should be done after a short digression.

Alan Turing, in a famous extended passage, invited us to watch a mathematician at work. She is equipped with a large notebook, a pencil, and an eraser. She writes or erases something on the page, or turns over some pages to find the result of a previous calculation, or turns over some pages to find a blank sheet to continue working on. These moves depend both on what she reads on the current page and on her thought processes (the state of her brain, if you like). Turing’s conclusion is that a mathematician is a Turing machine, since these actions are exactly what the eponymous machine does.

Not so long ago, I described how Ron Aharoni also invited us to watch a mathematician at work, in order to contrast with a poet at work. Rather than the extreme busyness of Turing’s mathematician, Aharoni’s spends most of his time staring into space.

Many eminent mathematicians, including Gauss and Poincaré, have left accounts of how they made their discoveries. I have collected some of these accounts. They are much closer to Aharoni’s mathematician than to Turing’s.

Anyway, Jack believes that mathematics is done in the manner Turing suggests, and consists of manipulations of words. So he would like a foundation of mathematics based on words and related directly to actual mathematical practice.

Natural numbers are the lengths of words, and so can be regarded as equivalence classes of words (two words being equivalent if their letters in natural order match up). Now addition can be defined by concatenation, and multiplication by substitution. (To multiply m by n, take a word of length m, and substitute a word of length n for each of its symbols.)

Now we have to choose what the basic assumptions are. Though I haven’t tried very hard, I suspect that proving the commutative law in this formulation would not be much easier than proving it in Peano arithmetic.

Any thoughts?

Posted in Uncategorized | Tagged , , , , , , , , | 3 Comments

Matroids and polymatroids

Jack Edmonds’ LTCC intensive course is now over. It differed in several respects from what was advertised. First, he shared the presentation with Alex Fink on a roughly equal basis; second, bimatrix games were shelved in favour of some exciting new developments in the area of matroid subdivision, leading up to a result of Lafforgue, who received a Fields medal for his work on the Langlands program. Seems incredible? Well, while I was at Permutation Patterns last week, Jack and Alex were teaching each other what they needed to know to make an attack on this development, and I hope that exciting things will be forthcoming.

I will give a very brief summary of the course content, leaving a lot out. I am completely unable to capture the complex dynamics between two remarkable mathematicians and speakers, and will not attempt much to tease apart their contributions – you should have been there!

Course material, and much more besides, is available here.

Polymatroids

We are working in n-dimensional real space, with basis indexed by a “ground set” E, which will carry some of the combinatorial structure.

A polymatroid set function is a function f from the power set of E (the set of subsets of E to the set of real numbers (though we often restrict to rationals or even integers) satisfying three conditions:

  • f(∅) = 0;
  • f is non-decreasing; that is, if A ⊆ B then f(A) ≤ f(B);
  • f is submodular; that is, for any two sets A and B, we have f(AB)+f(AB) ≤ fA)+f(B).

Submodular functions have wide applicability, perhaps partly because the condition means that the utility of a new element e relative to a set B is not more than its utility relative to a proper subset A. In any case, Jack explained how to find the optimum value of a submodular function by reducing it to a polymatroid set function.

A polymatroid set function defines a polyhedron in RE consisting of those vectors x with non-negative components which satisfy x(A) ≤ f(A), where x(A) means the sum of the coordinates of x lying within the subset A of E.

This polyhedron is defined by exponentially many linear inequalities, which sounds like bad news; but its vertices can be found efficiently by the greedy algorithm (which, as Jack pointed out, was devised by the Czech mathematician Borůvka).

Matroids

There are many ways to define a matroid. Jack was somewhat scathing about books which laboriously prove the equivalence of definitions in terms of independent sets, bases, circuits, hyperplanes, rank function, and so on. I am perhaps guilty, but I think that a couple of definitions I have drawn attention to are rather more suprising.

A matroid here is defined by its rank function. This is a polymatroid set function with two extra properties: its values are non-negative integers; and f(A) ≤ |A| for all subsets A. The independent sets of the matroid are just the sets for which equality holds here.

In the other direction, given any polymatroid set function f, we can define a matroid by the rule that its independent sets are those sets A for which f(S) ≥ |S| for all subsets S of A.

The prototypical example of a matroid is given by a matrix (hence the name): we take E to be a set indexing the columns of the matrix, and a subset A is independent if and only if the corresponding columns are linearly independent.

Jack said that there are three areas of matroid theory in which important work is going on today:

  • optimization;
  • representability (by a matrix over a field, as above);
  • connections with algebraic geometry (touched on below).

Matroid representability over finite fields is the subject of a major piece of work by Geelen, Gerards, and Whittle, which will hopefully be published soon. (According to Geoff Whittle, they have found a path through the wilderness, and need now to construct a decent road so that others can travel that way.)

A matroid rank function is a particular examplel of a polymatroid set function, and so it defines a polytope, sometimes called a matroid polytope. Its vertices are precisely zero-one characteristic vectors of the independent sets of the matroid. For this reason it is sometimes called the independent set polytope of the matroid. Later we will meet another polytope, the base polytope.

Matroid sum

It is clear that the sum of polymatroid set functions is a polymatroid set function. So in particular, if M1, …, Mr are matroids on the same ground set E, then the sum of their rank functions is a polymatroid set function. By the construction of the preceding section, it gives rise to a matroid, called the matroid sum of the given matroids.

How do we recognise the independent sets of a matroid sum? It turns out that the following two conditions on a set A are equivalent to its independence in the sum, and hence to each other:

  • for every subset S of A, f1(S)+…+fr(S) ≥ |S|;
  • A can be partitioned into subsets A1, …, Ar such that Ai is independent in Mi for i=1,…,r.

This is the matroid sum theorem or matroid partition theorem. It is an example of what Jack calls a “good characterization”: the second condition provides a short certificate for the independence of A (the partition into independent sets of the matroids), and the first provides a short certificate for its failure (the existence of a set S failing this inequality).

Transversal matroids

Here is a simple application. Let G be a bipartite graph, with r vertices on the left and n on the right. Call a subset of the right vertices independent if it has a matching to the left vertices. These sets are the independent sets of a matroid, called a transversal matroid.

For i=1,…,r, let Mi be the matroid on the right vertices, where the rank of a set is 1 if some right vertex is joined to the ith left vertex. This is a very simple rank 1 matroid; and the transversal matroid defined by the graph is the sum of the matroids M1, …, Mr.

For this example, the matroid sum theorem reduces precisely to Hall’s marriage theorem.

Another application involves the sum of k copies of the usual graphic matroid of a connected graph G, whose independent sets are the edge sets of forests. The matroid sum theorem gives a condition for a graph to have k edge-disjoint spanning trees, which is a theorem of Nash-Williams.

Matroid intersection

By the intersection of two matroids on a given ground set, we mean the structure given by the subsets which are independent in both matroids. I think this is not in general a matroid, though it is in some special cases. But it does have a remarkable property, the matroid intersection theorem, which states that the intersection of the two matroid polytopes is a polytope whose vertices are just the characteristic vectors of the sets which are independent in both matroids. (This is Jack’s favourite theorem.)

Here is an application. Let G be a connected directed graph on n vertices which has a distinguisued vertex r, the root. A branching of G is a spanning tree in which each edge is directed away from the root. Now branchings are the sets of n−1 edges which are independent in both of the following matroids:

  • M1, the usual graphic matroid of G;
  • M2, the matroid in which the rank of a set is the number of vertices which have an entering edge from the set (note that each vertex other than the root has exactly one entering edge in a branching). (This matroid, incidentally, is the sum of n−1 matroids of rank 1.)

By taking the sums of k copies of each of these matroids, we obtain a test for a directed graph to have k edge-disjoint branchings.

The reason why we cannot expect a nice result for the intersection of three matroids is that, in the above, if we take M3 to be the matroid where the rank of a set of edges is the number of vertices with an edge of the set leaving the vertex, then a set of n−1 edges independent in all three matroids is precisely a Hamiltonian path; it is difficult to find Hamiltonian paths. So we cannot expect an efficient algorithm.

Matroid subdivision

Here we decompose, not the combinatorial structure, but the polytope associated with a matroid. This does not work for the independent set polytope, since such a polytope contains a neighbourhood of the identity, which cannot be shared among the pieces. So we use the base polytope instead.

I discussed Alex’s favourite example of this here. The base polytope of U2,4 is an octahedron, whose vertices are indexed by the 2-element subsets of {1,2,3,4} (the bases of the uniform matroid). The kind of subdivision we are interested in corresponds to cutting the octahedron along one of its planes of symmetry to form two square prisms: each is the base polytope of the matroid on 4 points in which all but one pair of points are bases.

Matroid base polytopes are characterised by the conditions that all its vertices are zero-one vectors and any edge is in the direction of the difference between two standard basis vectors. (This is the translate of the exchange property into polytope language.)

One reason why subdivisions are important is that the Tutte polynomial of a matroid is additive over subdivisions.

There is an important class of subdivisions called regular. One of these arises as follows. Add an extra dimension to the space, and “raise” each vertex of the matroid polytope by a certain distance in the extra dimension. Some extra faces have to be added if the function giving the distances is not affine (the polytope will gain extra folds when it is lifted up). Projecting the “lower” faces of the lifted polytope gives a regular subdivision of the original one.

It is not immediately clear that this procedure produces a subdivision; but it turns out that it does. For example, if we fix five vertices of the octahedron and lift the sixth by 1 (in the fourth dimension), we obtain the subdivision into two square pyramids.

Now the remarkable result of Lafforgue, which connects with toric varieties in algebraic geometry and also with the assignment problem, is the following. Consider matroids represented by vectors in a real vector space. There are two operations on the vectors which clearly doesn’t affect the matroid: applying an invertible linear map to the vector space; and scaling the representing vectors by non-zero constants. We say that the representation is deformable if there are continuous motions of the vectors, not a combination of the above types, which preserves the matroid.

Theorem If a matroid represented over the real numbers is deformable, then it has a nontrivial subdivision.

Alex gave us as an example the Desargues matroid, the usual Desargues configuration as a rank 3 matroid where the dependent 3-sets correspond to the lines of the configuration. He showed us how to do the computations by hand or by using software.

Posted in events, exposition | Tagged , , , , , , , , | 2 Comments

Apology – out of contact

I’m afraid that, because of several emergencies (including a serious computer breakdown) I will be out of contact for an indefinite time. I will not be able to respond to email except perhaps sporadically.

I hope things will be back to normal soon but I make no promises.

Posted in Uncategorized | Leave a comment

Permutation patterns, days 3-5

I never promised to write something every day …

Anyway, the conference is now over. The LMS conference wi-fi was just not up to the demands of a conference big enough to fill the Hardy room, so lots of on-line things didn’t get done.

So, briefly, a few highlights.

On Wednesday, Vince Vatter gave an expository talk on Joseph Fox’s proof. I will try to describe the background.

One of the earliest concerns of researchers in permutation patterns was: how many permutations lie in a given downward-closed class? Such classes may be defined by excluded sub-patterns, by constructions from smaller classes, or as the output of some computational device. (One of the earliest results, by Don Knuth, was that permutations which can be generated by a stack with optional bypass are counted by the Catalan numbers.) One of the first big targets was the Stanley–Wilf conjecture, stating that the class defined by a single excluded pattern contains exponentially many permutations on n points: that is, if an is the number of such permutations, then (an)1/n tends to a finite limit c as n tends to infinity. Since 2002, this conjecture is the Marcus–Tardos theorem.

Attention then turned to the question: what are the possible growth constants c, if the forbidden pattern has length k? We don’t even know the complete answer for k = 4, as I reported here. But on the basis of very limited information, a couple of conjectures were made suggesting that there was an upper bound which was quadratic in k. This was refuted by Jacob Fox, who showed that there are patterns of length k for which the growth constant is fractional exponential in k and, moreover, that for large k almost every pattern has growth rate at least this large.

Vince gave an exposition of the proof, which involves a number of original ideas, including a very clever encoding of permutations as matrices, a notion of interval minor order, Cibulka’s theorem, and a random construction.

Mike Albert gave a talk with the subtitle “How I learned to stop worrying and love the machine”, on a very general approach to generating permutations by a “computational” device. Really it is a construction which takes a permutation pattern class and produces a larger one. In Knuth’s example mentioned above, a stack can by itself produce only the reversing permutation, but the addition of a bypass (so that we may move things directly from input to output) allows all 231-forbidding permuations as output. This gives a very interesting perspective on Wilf-equivalence (two permutation classes are Wilf-equivalent if their enumeration functions are equal) and explains the ubiquity of Catalan and Schröder numbers in counting permutation classes, for example.

The conference dinner on Thursday was held on a boat moored on the Thames near the Hungerford Bridge.

Big Ben

Factoid from the last day: From Cyril Banderier’s talk, I picked up the following. The number of permutations of {1,…,n} with k left-to-right maxima is equal to the number with k cycles (and so are counted by the Stirling numbers of the first kind). The simple bijection, due to Foata, I believe, from cycles to lr-maxima works like this. Take the permutation in cycle form. Start each cycle from its greatest element. Then order the cycles so that these greatest elements increase. Then simply delete the brackets and regard the sequence of numbers as a permutation. The largest points in the cycles are the lr-maxima. Conversely, given a permutation in passive form with the lr-maxima marked, cut before these and insert brackets )( at these points, with ( at the start and ) at the end.

Cyril explained that permutations with at most d non-lr-maxima are precisely those which can be produced from the identity with d “jumps”, where each jump takes one element and moves it any number of places to the right, moving the intervening elements back one place. This process is related to a model for gene mutation by transpositions.

Slides of the talks will be put on the conference web page. Mine are already posted in my own list of talks given.

So thanks to Robert Brignall and David Bevan for putting on a very nice conference, which just fitted into the Hardy Room at De Morgan House. Especially to Robert, who had to miss part of the conference because his son was born during the meeting!

Posted in events | Tagged , , , , , , , | Leave a comment