Monthly Archives: August 2012

Looking Again at Erdős’ Discrepancy Problem

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. Discrepancy theory is a wonderful theory and while I am not an expert we had several posts about it here. (This post on Beck-Fiala and related matters; and this news item on Beck’s 3-permutation conjecture.) I am aware of at least one important recent development in the theory that I did not report.  My posts go around the problem and do not attack it directly but I hope people will have a chance to think about the problem again and perhaps also about polymathing again. Meanwhile, polymath7 (over the polymath blog) is in a short recess but I hope a new research thread will start soon.

Tokyo, Kyoto, and Nagoya


Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing. Added later: Mazi and I at the same restaurant taken by Stanley.

I just returned from a trip to Japan to the FPSAC 2012 at Nagoya and a workshop on convex polytopes in Kyoto. As in my first visit to Osaka in 1999 I found Japan stunning, and this time I was able to share the experience with my wife.

Kyoto: The week before FPSAC there was a workshop at RIMS devoted to convex polytopes. Some highlights: A classical result by Venkov and McMullen characterizes polytopes whose translates tile the Euclidean d-space.  Sinai Robins talked about his work with Nick Gravin and Dima Shiryaev about k-tilings (every point is covered k times).  Not a full characterization yet but already some impressive results. Gunter Ziegler talked about his work with Karim Adiprasito disproving an old conjecture by Shephard which asserts that there are only finitely many projectively unique d-polytopes for every dimension d. This is false above dimension 81.  Eran Nevo talked about his solution with Satoshi Murai of the generalized lower bound conjecture and some subsequent works on triangulated manifolds. There were several talks relating Ehrhard polynomials of polytopes with enumerative combinatorics,  and several talks on algebraic geometry, toric varieties, Fano varieties, and mirror symmetry. Here are the slides of my lecture entitled open problems on convex polytopes I’d love to see solved (but some further explanations for some parts are needed). I hope to return to some of the topics of the workshop in a later post.

Nagoya: FPSAC (Formal power series and algebraic combinatorics) is a central annual  combinatorial meeting with special emphasis on enumerative and algebraic combinatorics. This year it was the 24th such event although I could have swear that I took part in an FPSAC in Montreal already in 1985 but apparently this was a conference with a similar flavor and different name. Much is going on in enumerative and algebraic combinatorics. Cluster algebras, miraculously discovered a decade ago by Fomin and Zelevinsky are going strong in combinatorics as well as in other areas. Alternating sign matrices continue to offer amazing problems and answers. There were quite a few lectures on representation theory, symmetric functions, random matrices, and also on relations of enumerative combinatorics with hyperplane arrangements with polytopes and with physics. There were lectures involving massive computations and new computerized method and packages for symbolic computations  were described. Here are the slides of my lecture entitled Discrete isoperimetry: problems, results, applications and methods. The program page now contains slides for most lectures.

What are alternating sign matrices?

I suppose that you all know what a permutation matrix is (an n by n matrix with 0,1 entries and one non zero entry in each row and each column) and alternating sign matrices are amazing generalization of permutation matrices discovered by William Mills, David Robbins, and Howard Rumsey. (See also this article by Bressoud and Propp) They are integral n by n matrices with 0,1 and -1 entries. In every row and every columns  the non zero aliments (and there must be at least one such element)  should alternate between 1 and -1 and start and end with a ‘1’. Alternating sign matrices are in one to one correspondence with monotone triangle. Thos are triangles of integers starting with a row: 1,2,…,n. With the following rules: (a) all rows are strictly increasing; (b) every element in row i is weakly between the two elements above it.

The amazing thing is that the number of alternating sign matrices of order n is precisely


This was a conjecture by Mills, Robbins and Rumsey and it took over a decade until it was proved by Doron Zeilberger. Later Greg Kuperberg found a short proof and by now several proofs are known. If you have some information or ideas on alternating sign matrices that you would like to share or some questions about them, or about anything else, please contribute a comment.