Tentative Plans and Belated Updates II

Elementary school reunion: Usually, I don’t write about personal matters over the blog, but having (a few weeks ago) an elementary school reunion after 42 years was a moving and exciting event as to consider making an exception. For now, here is a picture:


Jirka’s Miraculous year

It looks like a lot is happening. From time to time I think that I should tell on my blog about exciting new things I hear about, but this is quite a difficult task. Perhaps I should at least post updates about progress on problems I discussed earlier, but even this is not easy.  Jirka Matousek wrote a paper entitled The dawn of an algebraic era in discrete geometry?  The paper starts as follows:

To me, 2010 looks as annus mirabilis, a miraculous year, in several areas of my mathematical interests. Below I list seven highlights and breakthroughs, mostly in discrete geometry, hoping to share some of my wonder and pleasure with the readers.

The paper lists seven startling new results. A few of these results were discussed here, a few others I have planned to discuss later, and yet a few others (like the recent solution by June Huh of the famous unimodularity conjecture for the coefficients of chromatic polynomials of graphs) caught me by a complete surprise. (Here is a link to a follow up paper by June Huh and Eric Katz.) Let me add one additional item, namely the solution (in the negative) by Boris Bukh of Eckhoff’s partition conjecture.

Other wonderful combinatorics news

These are also good times for other areas of combinatorics. I described some startling developments (e.g., here and here and here) and there is more. There were a few posts (here and here) on the Cup Set Problem. Recently Michael Bateman and Nets Katz improved, after many years, the Roth-Meshulam bound.  See these two posts on Gowers’s blog (I,II). Very general theorems discovered independently by David Conlon and Tim Gowers and by Matheas Schacht show that many theorems (such as Ramsey’s theorem or Turan’s theorem) continue to hold for substructures of sparse random sets.  Louis Esperet, Frantisek Kardos, Andrew King, Daniel Kral, and Serguei Norine proved the Lovasz-Plummer conjecture. They showed  that every cubic bridgeless graph G has at least 2^(|V(G)|/3656) perfect matchings. The concept of flag algebras, discovered by Razborov, is an extremely useful tool for extremal set theory. It has led to solutions of several problems and seems to bring us  close to a solution of  Turan’s Conjecture (which  we discussed here and here.) For example, it led to the solution by Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov of the question on the maximum number of pentagons in triangle-free graphs.  Hamed Hatami found a structure theorem for Boolean functions with coarse thresholds w.r.t. small probabilities. This extends and sharpens results by Ehud Friedgut and Jean Bourgain. I finally caught up (thanks to Reshef Meir) with Moser-Tardos result giving a new algorithmic proof for Lovasz local lemma. Amazing! You can read about it here.

Some updates on my Internet questions

Imre Leader and Eoin Long wrote a paper entitled tilted Sperner families, which solves a question I raised in the context of polymath1. Imre and Eoin give additional results and conjectures. My motivation was to try to come up (eventually) with very very general conjectures which include density Hales-Jewett as a very special case and are also related to error-correcting codes. Raman Sanyal discovered a dual form of Tverberg’s theorem in terms of families of fans.  (We asked about it here.) There is a new paper on the Entropy-Influence conjecture entitled The Fourier Entropy-Infuence Conjecture for certain classes of Boolean functions, by Ryan O’Donnell, John Wright, and Yuan Zhou, The paper contains a proof of the conjecture for symmetric Boolean functions and  various other cases. This is the first new result on the conjecture for many years. Also there is nice progress for the AC^0-prime number conjecture asked about in a previous post, and a subsequent Mathoverflow question (There I will keep updating matters.). Ben Green solved the conjecture! Jean Bourgain settled the more general MO question and also found results on certain AC(2) circuits.

Newton Institute and Oberwolfach,

And it seems that things are moving along nicely in other areas close to my heart.  A week ago (This was actually two months ago)  I participated in a workshop at the Newton Institute on discrete harmonic analysis. And in the first week of February we had our traditional Oberwolfach meeting on geometric and topological combinatorics. Many interesting results!

A visit to IQI

In the last week of January I visited Caltech. I missed the IPAM meeting scheduled a week before because my visa arrived too late but I still made it to IQI. This was a very nice opportunity as most of my time at Caltech was devoted to quantum information/quantum computation issues related to my own work on quantum fault tolerance. So I gave an “informal” seminar describing my point of view (and gave it again the next day at USC). Here are the slides.  My lecture was followed by two-hour discussion of the more technical details of my conjectures, seeking weak points and counterexamples in what I said, and trying to associate it with physics. There followed further discussions about some aspects of quantum fault tolerance and more general questions of quantum information with John Preskill, Leonard Schulman, Daniel Lidar and a few other people. (A lot of brilliant young people!) I learned quite a lot and was happy with this opportunity. (Of course, I did talk a little with Caltechian old and new friends about bona fide combinatorics questions.)

Three jokes for a dollar

On the weekend I took the LA metro (whose mere existence surprised me) and visited downtown LA and Hollywood. Next to Pershing station a person stopped me and asked if I want to buy three jokes for one dollar. I first said no, but then I reconsidered, called him back and gave him a dollar. To his disappointment and mine I did not understand the first joke, but the other two (perhaps adjusted to my revealed level of understanding) were quite good.

Hectic semester at HUJI

Here at Huji things are as hectic as always with 10-15 weekly research seminars. This week (This was two months ago; the semester have just ended). I went to three talks and they were very good which immediately led me to regret not coming to more lectures. Two weeks ago Gunter Ziegler gave the three Erdos’s lectures. One lecture entitled On 3n points in the plane is  quite similar to Gunter’s recent Notices paper with the same title. Gunter also gave a special popular lecture on “Proofs for the Book”.  There has also been quite intensive activity in algorithmic game theory (you can read about it here), quantum computation (a lot of visitors in recent weeks), and theoretical CS.


Overall, I don’t have that many more plans for the blog compared to the situation when I wrote this early plan and updates post. Nevertheless, here are some plans:

Polymath3: A new post is coming.   I posted a new post with a topological approach. I dont know if we should try to go back to the abstract problem.

Polymath1,4,5: There are more spin-offs of the old polymath projects I plan to write about, in particular on some polymath5 ideas possibly on Gowers’ blog.

Around Borsuk’s conjecture: A series of 2-3 posts about problems related to Borsuk’s conjecture are already half-written.

Football and taxi stories: A new way to revolutionize football is coming  has appeared. One of the purposes of taxi-and-other stories and mathematics-to-the-rescue stories was as a tool to waste immediately any reputation which I may gain on this blog (e.g., the embarrassing yet educational pills story followed immediately the first comment by Tim Gowers on this blog). The Layish story, which was indirectly referred to in the very first post will mark a new stage in the reputation-waste agenda.  (Along with a few other stories involving me and Avi W.) Also we are negotiating with Michal linial for more of her wonderful stories.

Update: The unthinkable happened. The Layish story is out.

Huntington library pictorial: This is certainly one of my most ambitious posts, and this explains why it takes so much time to write.  It addresses a long-standing problem which becomes more acute with time:

How to show pictures in a non-boring way.

The planned post will be a pictorial description of a tour from fall 2009, guided by Benny Sudakov, of the Huntington Library in Pasadena.

Mathematical snapshots from India: In my post about ICM 2010 and India I hardly mentioned any mathematics. A separate post is planned to present a couple of mathematical snapshots from India. Not so much from the lectures themselves as from accidental meetings with people. The two big problems in analysis according to Assaf Naor as told at the Bangalore airport while we were waiting for a flight to Hyderabad, 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: elliptic analogs) as explained by Eric Rains.

Proofs: There are proofs that I like to present (like this one), and I plan to present here a few more proofs:  A proof of KKL’s theorem that is mentioned here; Alon-Kleitman’s proof of the Hadwiger-Debrunner conjecture; and a famous proof by Perles which uses lice.

Contingency tables. Sasha Barvinok gave an illuminating talk at Yale in October 2008 about contingency tables, and this is a very nice story with many facets.  It started with a paper of Diaconis and Efron, which was followed, to a mathematician’s envy, by several papers criticizing their proposal, and a rejoiner. It is fortunate that I did not post about it at the time, since a lot has happened afterwards.  The same talk and visit led to a fruitful collaboration between Sasha and J.A. Hartigan.

(The Diaconis Efron’s paper: Diaconis, Persi and Efron, Bradley Testing for independence in a two-way table: new interpretations of the chi-square statistic. With discussions and with a reply by the authors. Ann. Statist. 13(1985),  845–913.   Here is a link to the article. You can find the nine papers discussing (rather critically) the original paper, and a rejoiner, which contains the great line:”This type of careless commentrary can be accepted in praise, but is unforgiveable in criticism.”   Here is a link to one of the paper by Barvinok-Hartigan)


Posets:  I still owe a post about partially ordered sets (POSETS) in the extremal combinatorics series (I,II,III,IV,VI).

f-vectors and homology: There was a series of posts about the g-conjecture and it seems like a good time to write about the relation between face numbers and topology (and mainly homology).

This entry was posted in Updates and tagged , , , . Bookmark the permalink.

6 Responses to Tentative Plans and Belated Updates II

  1. Nets says:


    Thanks for the publicity. But I must correct you that my coauthor on the Roth-Meshulam result is Michael Bateman.
    His other work can be found here:




    GK: So sorry Nets and Michael. It is corrected now.

  2. Pingback: Weekly Picks « Mathblogging.org — the Blog

  3. anonymous says:

    some typos?:
    – “every cubic bridgeless graph G has at least 2^(…) perfect matchings.”
    – “discovered by Rasborov”

  4. Pingback: A Couple Updates on the Advances-in-Combinatorics Updates | Combinatorics and more

  5. glancing says:

    Another typo?: Lovasz-Palmer conjecture –> Lovsaz-Plummer conjecture.

  6. Pingback: Updates and plans III. | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s