I was at the Pretty Structures conference in Paris last week.
The original conference in what became this sequence was called Pretty Things. Perhaps this is not serious enough for a meeting held at the Institut Henri Poincaré, I don’t know; but in any case, the name has now changed. The original meeting celebrated the birthday of Jack Edmonds; he is now a fixed point of these meetings. I will talk a bit about his contribution below.
As you will see from the conference web page, the meeting was in an institute named after Poincaré, in a street named after the Curies; the lectures were in a room named after Hermite, and the library is named after Borel. Nobody does it like the French!
The conference is done with virtually no organisation: no expenses, no name badges, no arranging of hotels, travel, conference dinners, or anything else. This would normally be fine. Unfortunately, in my case, a few things went wrong, and the whole conference narrowly avoided being a nightmare. Perhaps, being rather too stressed at work, I wasn’t sufficiently aware of problems before they hit. Anyway, I don’t want to recall all that; back to the conference itself.
The participants were for the most part either graph theorists or combinatorial optimisers, so I felt a bit out on a limb. I gave two talks about “Derangements”, a topic which has some very interesting algorithmic aspects, as well as links with pretty structures in other parts of mathematics, as I have described before on this blog. In the third lecture, as a result of a vote (taken using “first past the post”), I talked about “Synchronization”.
There were some very pretty structures indeed presented by some of the speakers. For example, Gérard Cornuéjols talked about Lehman matrices. A Lehman matrix is a square zero-one matrix A such that there is another square zero-one matrix B for which ABT = kI+E, where E is the all-1 matrix. Transposing, we see that B is also a Lehman matrix. These pairs form bridges between topics in finite geometry such as finite projective planes and Moore graphs, and topics in optimization such as the integrality of the set cover polytope for a family of sets. I chose the word deliberately, since these matrices were studied by Bridges and Ryser a quarter of a century before Lehman.
Briefly, the two sides of the bridge can be described:
- If A = B, then A is the incidence matrix of a finite projective plane (and conversely); we don’t know for which values of k these exist! If A is symmetric and B = A+I, then A is the adjacency matrix of a Moore graph of diameter 2; and, by a theorem of Hoffman and Singleton, we must have k=2, 3, 7 or 57 (the graphs are unique in the first three cases and existence is unknown in the fourth).
- Given a zero-one matrix M (the incidence matrix of a family of sets), the set cover polytope is the set of vectors x with all coordinates in [0,1] satisfying Mx≥1. Call M ideal if this polytope has integral vertices. Lehman showed that a minimally non-ideal matrix has a set of rows forming a Lehman matrix.
Gérard’s slides are here.
Another pretty thing was described by Jack Edmonds and Kathie Cameron. (Kathie is no relation of mine, as far as we know, though Cameron’s Cameron number is 2.)
The story was that two big results about games in economics, the existence of Nash equilibria for bimatrix games and Scarf’s fractional stable allocation theorem for coalitions where each player has a preference order on the coalitions to which (s)he belongs, can both be proved using a simple idea which has other applications too.
(I hadn’t realised that Nash’s proof was not algorithmic. An algorithm was found fairly recently by Lemke and Howson; this algorithm, much simplified, is what comes out of the new approach.)
A d-dimensional simplicial complex consists of a collection of (d+1)-element subsets (which they call rooms) of a set of vertices. A d-element subset of a room is called a wall. For d=1, such a complex is a graph; the rooms are edges and the walls are (non-isolated) vertices.
Now generalising the definition of an Eulerian graph, they define an Euler complex to be a simplicial complex in which every wall lies in an even number of rooms. A special case is that in which every wall lies in exactly two rooms; these comlexes are pseudomanifolds, and there are many interesting examples.
They call an Euler complex an oik for short; this is a pity, since the word “oik” is a handy term of abuse, but now I know that it is used for such a nice mathematical object I won’t be able to use it in this sense.
To cut a long story short: given a family (F1,…,Fk) of oiks on the same vertex set V, a room partition is a partition of the vertex set into k parts, where the i-th part is a room of Fi. A near-partition is similar, except that one vertex is not covered while another is covered twice. Now “exchanging” two vertices defines an adjacency on the set of all room partitions and near-partitions, giving the exchange graph. It can be shown that the partitions have odd valency in this graph, while the near-partitions have even valency. Hence there is always an even number of partitions; and a walk starting at one of them will end up at a different one, so given one room partition there is a simple algorithm to find another.
With this approach they show that the Lemke–Howson algorithm is exponential in the worst case. It is not known whether there is a polynomial-time algorithm for finding a Nash equilibrium. We are in a similar position to that in linear programming, once it was known that the simplex method is exponential in the worst case, but before Khachian and Karmarkar produced polynomial algorithms.
I was reminded of the Jacobson–Matthews random walk method for choosing a random Latin square. They also enlarge the space by admitting improper Latin squares (with a single impropriety). They are not so fortunate as to be in a situation where the proper Latin squares have odd valency and the improper ones even valency in the transition graph; but the valency depends only on whether the square is proper or improper, and the graph is connected, so the random walk converges to a distribution which, conditioned on properness, is uniform.
Among other nice things, I’ll just mention two talks on symmetry by Achill Schürmann. In the first, he made a bridge from symmetry to social choice. How many voting patterns are there (i.e. numbers of candidates expressing any given preference order) for which the result exhibits some paradoxical outcome such as the Condorcet paradox (intransitive pairwise ordering)? For a fixed number of voters, the outcomes live in a space of dimension n!−1 (where n is the number of candidates), which is rather large; but symmetry can make the computations feasible for small n. (This led to a discussion of the British referendum on our voting system.)
He used the theorem of Ehrhart (1967), asserting that the number of points in N.P, where P is a polyhedron with rational vertices and N a positive integer, is pseudo-polynomial in N (that is, polynomial on residue classes modulo m, for some m); the degree of the polynomial is the dimension, and the leading term the volume of P. This theorem, known to mathematicians, was “rediscovered” in social choice theory fairly recently.
In his second lecture, he showed us some beautiful configurations of points on the unit sphere, including the shortest vectors in the Gosset and Leech lattices and some of their subconfigurations, which minimise the total energy for all “reasonable” energy functions. The proof used stuff familiar to me: spherical codes and designs.
For devotees of mathematics and poetry, I offer the following phrase from a lecture of Nicolas Trotignon:
A nightmare about wheels
Shades of Ezekiel!
Some of the talks are already on the conference web page, and more should be posted eventually. My notes on derangements are there, with a pointer to the synchronisation notes from last year.
After the close of the conference we had a little party for Kristina Vuskovic’s birthday. I found myself giving a fourth lecture, briefly explaining the classification of the finite simple groups. Everyone agreed that it is not different in principle from some of the long “minimal counterexample” proofs in structural graph theory (Kristina’s topic).
In addition, Jack and Kathie took us to the opening of an exhibition by an artist friend of his, Paella Chimicos, or Paella ? as he later called himself. Stunning stuff. Jack persuaded the artist to autograph a copy of a book I bought there, and he personalised it with a drawing of an artist in a stripy T-shirt (someone had remarked that in England this suggests Burglar Bill, quite different from its connotation in France, and Paella himself happened to be wearing one), with the disturbing caption “Painting makes free!”