Updates from Cambridge

Combinatorics and more 2024-04-15

I am writing from Cambridge, UK, where I participated in an impressive conference celebrating Tim Gowers’s 60 birthday and I an about to take part in a satellite workshop of Theoretical computer science. Coming here was my first travel since the start of the war on October 7, and earlier today (April 14, around 02:00) we were witnessing a major dangerous escalation of the war with a direct Iranian drone and missile attack on Israel.

gif

(The sky in Israel during the attack source: Haaretz.)

The group photo of the conference. (Tim Gowers is second on the right on the first row.)

Let me tell you a little about the conference. This was an opportunity to meet old friends, to have very interesting conversation with some new friends, and to witness many young stars. I suppose that most talks will be soon on you Tube, but in the meantime Ryan O’Donnell’s lecture (that was given by Zoom) on random reversable circuits is already on the air in Ryan’s great You-tube channel. Incidentally, I spent much effort on studying random quantum circuits that Ryan mentioned in his talk and my previous post Random Circuit Sampling: Fourier Expansion and Statistics was devoted to their study using analysis of Boolean functions which is also a common interest of Ryan and me.

Avi Wigderson was scheduled to talk on Wednesday and a few hours before his talk we heard the news that Avi won the Turing award this year! Congratulations, Avi! This is also great news for the theoretical computer science community and for Israeli mathematical community. Avi and his work are frequently mentioned on my blog. This is also a good opportunity to congratulate Michel Talagrand who was awarded the 2024 Abel Prize, and Vitali Milman and Yanki Ritov who were awarded the Israel Prize this year.

avi3

The counterexample to the Daisy Conjecture

The first talk was by Imre Leader and he showed the disproof by David Ellis, Maria-Romina Ivan, Imre Leader of the Daisy conjecture. (Here is the link to the paper.) A daisy is an $r$ -uniform hypergraph with six edges. All these edges contain a common set of $(r-2)$ vertices and in addition each edge contains a pair of vertices from four additional vertices. (You can think about the daisy as $(r-2)$ -fold cone over $K_4$ .

The question was about the maximum number of edges of an $r$ -uniform hypergraph that does not contain a Daisy. The conjecture was that the density of such a hypergraph must tend to zero as $r$ tends to infinity. The crucial ingredient in the example is the following construction: Take $n=2^r-1$ and consider the vertices as the nonzero points in $V=F_2^n$ and the edges as bases in $V$ . Consider $r-2$ linearly independent vectors and suppose that they span the vector space $W$ . Let $a,b,c,d$ by four additional vectors in $V^*$ and let $\bar a, \bar b, \bar c, \bar d$ be their images in the 2-dimensional quotient $V/W$ .

If $(v_1,v_2,\dots, v_{r-2} a,b)$ , $(v_1,v_2,\dots, v_{r-2} a,c)$ , $(v_1,v_2,\dots, v_{r-2} a,d)$ , $(v_1,v_2,\dots, v_{r-2} b,c)$ , $(v_1,v_2,\dots, v_{r-2} b,d)$ , and $(v_1,v_2,\dots, v_{r-2} c,d)$ form bases in $V$ then $(\bar a, \bar b), ~(\bar a, \bar c)$ , $(\bar a, \bar d), (\bar b, \bar c)$ , $(\bar d, \bar d),$ and $(\bar c, \bar d)$ are all bases in the two-dimensional vector space $V/W$ and this is impossible.

Polymath project?

We also talked a little about possibilities for a new polymath project. Suggestions are welcome. Stay tuned.