Postoctoral Positions Available

Maybe I should say that (like every year but even more so) we do have funding for 1-2 postdoctoral positions in combinatorics, for 1-3 years starting in the next academic year (the time is flexible) here at the Hebrew University of Jerusalem. If you do research in combinatorics or in related areas you may enjoy our special environment (and weather, and sights), our lovely group of combinatorialists both in the mathematics and the computer science departments, and the other great reseach groups around. (We can supply recommendations from people who enjoyed it here and had a fruitful time.)

We can also support short term visits of graduate students and postdocs.

If you are interested, especially if you are (more or less) interested in the type of things I am doing – please send me an email. (Maybe write in the subject: “postdoctoral position in combinatorics”.)

Dorit Aharonov’s on TEDx: A Feldenkrais lesson for the beginner scientist

Here is a lovely lecture starting with quantum computers, going through the Feldenkrais method, and ending with a mathematical puzzle.

Click on the picture for the video of the talk.

Here are Dorit’s four body-mind principles for learning:

1. Start within your comfort zone and make it even more conforting,

2. Not too easy not too hard, pick an interesting challenge within your reach,

3. Move away from your desired place and come back to it from different angles,

4. Play with it, connect it with other things you know, make it your own.

Angry Bird Skepticism

Lenore Holditch is a freelance writer. Here is what she wrote to me: “I love learning about new topics, so I am confident that I can provide valuable content for your blog on any topic you wish, else I can come up with a post most relevant to your blog theme. The content would be fully yours.” Lenore only asked for a link back to her site . She sent me also a few of her articles like this one about finding jobs after graduation and this one about video games for training.

I asked Lenore to explore the following issue and she agreed:

Is the game Angry Bird becoming gradually easier with new versions so people get the false illusion of progress and satisfaction of breaking new records?

Stay tuned!

The Privacy Paradox of Rann Smorodinsky

  

The following paradox was raised by Rann Smorodinsky:

Rann Smorodinsky’s Privacy Paradox

Suppose that you have the following one-time scenario. You want to buy a sandwich where the options are a roast beef sandwich or an avocado sandwich. Choosing the sandwich of your preference (say, the avocado sandwich) adds one to your utility, but having your private preference known to the seller,  reduces by one your utility. The prior people have on your preferences is fifty-fifty.

If you choose the avocado sandwich your utility is zero, hence you can improve on this by picking each type of sandwich at random with probability 1/2. In this case your private preference remains unknown and you gain in expectation 1/2 for having the sandwich you prefer with probability 1/2.

But given this strategy, you can still improve on it by choosing the avocado sandwich.

Happy Birthday Ron Aharoni!

Ron Aharoni, one of Israel’s and the world’s leading combinatorialists celebrated his birthday last month. This is a wonderful opportunity to tell you about a few of the things that Ron did mainly around matching theory.

Menger’s theorem for infinite graphs

Hall’s marriage theorem

Hall marriage theorem (Philip Hall, 1935) gives a necessary and sufficient condition for a perfect matching in bipartite graphs. Suppose that you have a set A of n men and a set B of n women and a list of pairs of men and women that know each other. A perfect matching  is a bijection from A to B which matches every man to a woman he knows.

Hall’s marriage theorem asserts that a necessary and sufficient condition for a perfect matching is that every set S of men knows together at least |S| women.

This is an extremely important theorem and the starting point for a wonderful matching theory. It is a primary example of combinatorial duality. Other theorems of this kind are Menger’s theorem on connectivity in graphs, Dilworth’s theorem (1950) on covering posets with chains, the max-flow min-cut theorem (1956), and quite a few more.

Menger’s theorem

Menger Theorem (Karl Menger, 1927). Let G be a finite  graph and let x and y be two distinct vertices. Then the minimum number of edges whose removal disconnects x and y is equal to the maximum number of pairwise edge-disjoint paths from x to y.

Infinite Menger

Ron Aharoni and Eli Berger proved the following theorem (here is a link to the arxived version):

Aharoni and Berger Theorem (2005): Given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A to B paths, and a separating set consisting of the choice of precisely one vertex from each path in P.

A Few Mathematical Snapshots from India (ICM2010)

Can you find Assaf in this picture? (Picture: Guy Kindler.)

In my post about ICM 2010 and India I hardly mentioned any mathematics. So here are a couple of mathematical snapshots from India. Not so much from the lectures themselves but from accidental meetings with people. (Tim Gowers extensively live-blogged from ICM10.) First, the two big problems in analysis according to Assaf Naor as told at the Bangalore airport waiting for a flight to Hyderabad.  Next, a lecture on “proofs from the book” by Günter Ziegler. Then, some interesting things I was told on the bus to my hotel from the Hyderabad airport by François Loeser, and finally what goes even beyond q-analogs (answer: eliptic analogs) as explained by Eric Rains. (I completed this post  more than two years after it was drafted and made major compromises on the the quality of my understanding of the things I tell about. Also, I cannot be responsible today for the 2-year old attempts at humor.)

The two big problems in analysis according to Assaf, and one bonus problem

Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture

This post is authored by Karim Adiprasito

The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction.  Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about  was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. In this post I want to outline a generalization of a beautiful result of Billera and Provan in support of the Hirsch conjecture.

I will consider the simplicial version of the Hirsch conjecture, dual to the classic formulation of Hirsch conjecture. Furthermore, I will consider the Hirsch conjecture, and the non-revisiting path conjecture, for general simplicial complexes, as opposed to the classical formulation for polytopes.

Theorem [Billera & Provan `79] The barycentric subdivision of a shellable simplicial complex satisfies the Hirsch Conjecture.

The barycentric subdivision of a shellable complex is vertex decomposable. The Hirsch diameter bound for vertex decomposable complexes, in turn, can be proven easily by induction.

This is particularly interesting since polytopes, the objects for which the Hirsch conjecture was originally formulated, are shellable. So while in general polytopes do not satisfy the Hirsch conjecture, their barycentric subdivisions always do! That was a great news!

Shellability is a strong combinatorial property that enables us to decompose a complex nicely, so it does not come as a surprise that it can be used to give some diameter bounds on complexes. Suprisingly, however, shellability is not needed at all!  And neither is the barycentric subdivision!

A simplicial complex Σ is called flag if it is the clique complex of its 1-skeleton. It is called normal if it is pure and for every face F of Σ of codimension two or more, Lk(F,Σ) is connected.

Theorem (Adiprasito and Benedetti):  Any flag and normal simplicial complex Σ satisfies the non-revisiting path conjecture and, in particular, it satisfies the Hirsch conjecture.

This generalizes the Billera–Provan result in three ways:

– The barycentric subdivision of a simplicial complex is flag, but not all flag complexes are obtained by barycentric subdivisions.

– Shellability imposes strong topological and combinatorial restrictions on a complex; A shellable complex is always homotopy equivalent to a wedge of spheres of the same dimension, and even if a pure complex is topologically nice (if, for example, it is a PL ball) it may not be shellable, as classic examples of Goodrick, Lickorish and Rudin show. Being normal still poses a restriction, but include a far wider class of complexes. For example, every triangulation of a (connected) manifold is normal, and so are all homology manifolds.

– Instead of proving the Hirsch conjecture, we can actually obtain the stronger conclusion that the complex satisfies the non-revisiting path conjecture, which for a given complex is stronger than the Hirsch conjecture.

A geometric proof of our theorem appeared in a recent paper “Metric geometry and collapsibility”  with Bruno Benedetti. . I will give here a short combinatorial proof.

Construction of a combinatorial segment

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post ”Perpetual Motion of The 21st Century?“ was followed by three posts by Aram. The first ”Flying Machines of the 21st Century?“ the second ”Nature does not conspire“ and the third “The Quantum super-PAC.“ We had then two additional posts ”Quantum refutations and reproofs” and ”Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: ”Quantum repetition“ and ”Quantum supremacy or quantum control?“

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is  and at most , and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the -prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.

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

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

1!4!7!…(3n-2)!/n!(n+1)!…(2n-1)!

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.