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 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 -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). Continue reading