Budapest, Seattle, New Haven

Here we continue the previous post on Summer 2010 events in Reverse chronological order.

Happy birthday Srac

In the first week of August we celebrated Endre Szemeredi’s birthday. This was a very impressive conference. Panni, Endre’s wife, assisted by her four daughters, organized a remarkable exhibition by mathematicians who are also artists. Panni also organized tours and activities for accompanying people which my wife told me were great. A few mathematicians chose to attend the tours rather than the lectures. In Hungary, Endre has a nickname “Srac” which means “kid”, and, to my amazement, people (including young people) really call him Srac.

Szemeredi Kati and Zsuzsa

After-dinner speech. The distinction between surprising and amazing, and the question of do we age when it comes to our emotions and inner soul experiences

Being asked to give the after-dinner speech for Endre in the festive boat dinner ranks second in my life among cases where I was chosen for a job for which so many others were much, much more deserving and qualified. Continue reading

Plans and Updates

Jerusalem and Budapest




Monday, last week was the last day of lectures for the spring term here at the Hebrew U.  One outcome of the long professors’ strike was a very fruitful year for research seminars. We ran them during the strike and we run when we taught. I heard about quite a lot of nice developments recently. Zeev Dvir gave a talk on the finite field Kakeya problem. The proof was extremely simple to start with (see Tao’s post ) and Zeev’s presentation was even simpler. It is a very interesting question how, given Dvir’s proof, we should now view the connection between the finite field version of the problem and the original problem. Does Dvir’s proof support the possibility that the original problem is not as hard as feared? Does it support the view that the finite case is not related to the continuous case? (Both Tao and Laba discuss these questions.)

I will tell you in very rough terms (which represent my partial understanding of the matter) one recent wonderful development I heard about.  Kolmogorov and Sinai proved that the Entropy is an invariant for Bernoulli shifts under isomorphism.  Ornstein celebrated isomorphism theorem  asserts that entropy is the only invariant. Orenstein and Weiss studied other group actions, and extended these theorems to amenable groups. There were strong indications that free-group actions behave very differently. (There were examples where the entropy function went the wrong way for “factors”.) However, Lewis Bowen has just shown that for free-group action entropy is an invariant! (OK, I oversimplified matters here for the sake of telling the story.) And he further proved a similar result for all “sofic groups”, a strange notion of groups which is a mixture of amenable and residually finite groups that, as far as we know, may include all groups. Benji Weiss told us about it in the “basic notions seminar”, and a few weeks later another lecture was given by the man himself – Lewis Bowen – who came from Hawaii for a short visit.

And last week I participated in a meeting “Building Bridges” in Budapest honoring Laci Lovász for his birthday. A lot of interesting talks on extremal combinatorics, graph theory, optimization, probabilistic combinatorics, and theoretical computer science. I will come back to this meeting later but let me mention one talk which I found very surprising: Peter Winkler talked about his work with Rick Kenyon on branched polymers. Kenyon and Winkler found startling simple combinatorial proofs to starling results of Brydges and Imbrie, and proved further results. I hope to add a link to the actual presentation. Hungary is the discrete mathematics superpower and on top of that as Einat Wigderson recently made clear “The Hungarians are also much funnier”.  It was nice to meet many old friends (and annoy them, at times, with silly jokes). Here is Micky Simonovits and here you can see Endre Szemeredi, Anna Szemeredi, Szemeredi’s jacket and Szemeredi’s tie. I followed the name of the conference and talked about mathematics of social choice.




We had a few slow weeks on the blog and as the saying goes: “If you cannot do, plan, and if you cannot plan, plan plans.” Together with a little summary of previous posts, I will describe some of the things I plan to write next on this blog.

I plan five posts in the series about Extremal combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult theorems which became quite easy in time. Extremal Combinatorics III will present several basic results in extremal set theory; Part IV will be about POSETS, and part V will present the Frankl-Wilson theorem, or, at least, special cases.

I gave four posts (I, II, III, IV) based on my lecture in Marburg, dealing with high dimensional Cayley formula. Richard Stanley gave a detailed remark on why the fantasy about weighted correct version of MacMahon’s conjecture for solid partitions is not what standard proofs of the plane partition case extend to. I plan a little series of posts on “f-vectors and homology,” which was the title of a paper with Bjorner in 1988 as well as of my talk in Stockholm.  However, before that I want to describe the “g-conjecture for spheres” a central problem in algebraic combinaorics.

We had several posts on convex polytopes.  I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.) The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm. I also updated the post on five open problems regarding convex polytopes and added two additional problems.

We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. Meanwhile, have a look at the very successful discussion on Secret Blogging Seminar about the shy and secretive mathematicians, and how they triumph again and again.

Let’s talk some more on economics and rationality. And about sociel welfare functions and voting methods. We discussed some controversies related to rationality in this post, and the Notices book-review about economics and common sense supplied a source for two posts (1,2).  I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. Sababa!

I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity. Meanwhile, let me link you to the classical post by Aaronson “Reasons to believe” (on why we believe that NP is not P). And while at it, look at “Reason to believe II” (on why many of us believe that quantum computers are feasible.) Read also Bernard Chazelle’s thoughts about alorithms and science.

The most successful link we had so far was  Continue reading

Brush Up Your Björner:


Just returning from a conference in Stockholm.

(Cole Porter: Brush up your Shakespeare - new lyrics by Kimmo Eriksson)

The girls today in society
go for great mathematics, see.
So to win their hearts you must quote with ease
Pythagoras and Archimedes.
One must know Newton and Gauss and, hey,
what’s his name, eh? Poincaré!
Unless you know Grothendieck and DesCartes
no sweet lady will give you her heart.
But to really make them fall
and to make your love-life surrealist,
quote the greatest of them all:
a 60-year old comb’naturrealist.

Brush up your Björner,
start quoting him now!
Brush up your Björner,
and the ladies you will wow.

Many women will find it admirable
if you tell her she makes your CHIPS FIRABLE.
If your lady-friend still isn’t yielding
say you’ve got this big place: a TITS BUILDING.
If there still is some source of estrangement
make some cozier SUBSPACE ARRANGEMENT.
Brush up your Björner,
and they’ll all be charmed!

Continue reading

Jerusalem Combinatorics ’93

Jerusalem Combinatorics ’93 is the title of a conference I organized that took place fifteen years ago in May 9-17, 1993 at the Hebrew University of Jerusalem. It was a conference that was devoted to all areas of combinatorics. The other organizers were Noga Alon, Hélène Barcelo, Anders Björner, and Edna Wigderson. Altogether there were around thirty plenary talks, and about fifty additional invited talks in 10 sections representing various subareas of combinatorics. There were also four special talks for a large audience. Overall, it was a fruitful and a very nice event that I think people enjoyed.

A special aspect of the conference was the unusually large number of female speakers. 16 out of the 30 main plenary speakers were women, and also many of the additional speakers,  special session organizers, and other participants. The four large audience lecturers were Vera Sós, who talked about irregularities of distributions, Mireille Bousquet-Mélou who talked about polyominoes, Hillel Furstenberg who talked about Ergodic theory and Combinatorics, and Joan Birman who talked about the combinatorics of finite-type invariants for knots.

collection of papers   by participants of the conference, edited by Barcelo and myself, appeared as Volume 178 of Contemporary  Mathematics.

The poster of the conference also has an interesting story behind it. Continue reading

A Meeting at Marburg

  Just returning from a cozy two days discrete-math workshop in Marburg. A very nice mixture of participants and topics. The title of my talk was “Helly theorem, hypertrees and strange enumeration” and I plan to blog about it sometime soon. A few hours before taking off, Aner Shalev told me that a 1951 conjecture by Ore asserting that every element in a non abelian finite simple group is a commutator have just been proved by a group of four researchers – Aner himself and Liebeck, O’Brien and Tiep.  (Ore himself proved that for A_n every element is a commutator.) The basis for a very complicated inductive proof required computer works and the final OK came four hours before Aner gave a lecture about it! 

The talks in Marburg were very interesting.

Day 1:Enumerative combinatorics techniques and results related to the asymptotic conjectured formula for the number of self avoiding random walks (a holy grail in statistical mechanics);  Continue reading