Mathematics (mainly combinatorics) related matters: A lot of activity.

Combinatorics and more 2023-05-08

Plan for next weeks blogging

There are various things to blog about and let me give a quick preview for the plan for the next few posts. The purpose of this post is to give an impression about the hectic mathematical activities around here with special emphasis on combinatorics and early-in-the-week activities. There is so much action around that I feel tired just to write about it. Next post will be around Amnon Shashua’s lecture at Reichman university giving a deep dive on LLMs. Following it I will tell you about developments around physics with special emphasis to the evening at the Israeli Academy celebrating Israel entrance to CERN. Fourth in line is a post about my recent paper with Yosef Rinott and Tomer Shoham on the Google 2019 quantum supremacy experiment (this is our third paper on the subject).

Let’s move on to today’s post which will include more than the usual dose of Hebrew.

Avinoam

A few weeks ago, Avinoam Mann, a dear member of our department in Jerusalem, passed away. Avinoam was a famous group theorist working on many aspects of this theory. I have many warm memories of Avinoam since I was a student when I took with Avinoam two very demanding reading courses, and later as colleagues and friends for many decades. Avinoam was also a poet and here is a poem he wrote.

Many many many Seminars

HUJI Combinatorics seminars

The seminar takes place on Mondays between 11-13. The 2-hour format allows ample discussions. There were brilliant talks at the HUJI (Hebrew University of Jerusalem) Combinatorics Seminar. The last four were given by Illay Hoshen, Yuval Filmus, Igor Balla, and Nathan Keller. Ilay Hoshen spoke about his paper with Wojtek Samotij on Simonovits’s theorem for random graphs, and presented a (partial) resolution to a conjecture by DeMarco and Kahn. Yuval Filmus talked about a joint work with Nathan Lindzey, where the starting point was Fourier expansion for function on the Boolean cube and asked what happens if we study functions on other domains, such as the “slice” or the symmetric group? (very elegant connection with representation theory.) Once it’s on the arxive we will add the link. Igor Balla talked about Equiangular lines via matrix projection. This work presents a definite progress on the classical problem of equiangular lines as well as some connections to problems in quantum information theory. Nathan Keller talked about his joint work with Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld. Hypercontractivity for global functions is used for far reaching Erdos-Ko-Rado theorems for permutations. Nati Linial wrote to me about the lecture: מצויינת, מדוייקת, אינפורמטיבית, א-מחיה . (which roughly translates to: “Outstanding, Accurate, Informative – Oh the Joy!”). Today Amir Yehudayoff will talk about his work with Dan Cameron on dual systolic graphs.

This is not the only HUJI combinatorics seminar, on Thursday afternoon we have a joint Jerusalem-Copenhagen combinatorics seminar and at noon we have a joint Jerusalem Copenhagen lunch seminar. I gave a lecture in the lunch seminar a couple of weeks ago about challenges in the combinatorial theory of convex polytopes and spheres beyond the $g$ -theorem. Of course, our CS-theory Wednesday seminars have plenty of lectures of combinatorial flavour.

Shachar Lovett’s lecture at Tel Aviv Combinatorics Seminar

Things in TAU (Tel Aviv University) are not calmer.

TAU combinatorics seminar is on Sundays 10:05-11:05, and last week (April 30) the legendary Shachar Lovett gave a talk about his paper with Alexander Knop, Sam McGuire, and Weiqiang Yuan about Structure of monomials of Boolean functions. (Click for the slides.)

The main theorem is the following one. Theorem: Let $f:\{0,1\}^n \to \{0,1\}$ be a Boolean function with $|M(f)|=m$ . ( $M(f)$ is the number of monomials in the presentation of $f$ ) Then f can be computed by an AND decision tree of depth $d=O(\log ^5m\log n)$ .

The proof uses an auxiliary (sharp) result about hitting sets (aka transversals) for monomials. It is not known if the $\log n$ factor in the main theorem is needed. Shachar described exciting connections with the log-rank conjecture and with Frankl’s union-closed conjecture. He also described the analogous (Fourier) question for functions $f:\{-1,1\}^n \to \{0,1\}$ .

After the lecture Shachar told me about some basic details of the recent amazing proof of Kelly and Meka for sharp bound for Roth’s theorems. Shachar promised me that the crucial new ideas giving a Fourier proof for similar bounds for the cup set problem could be presented in four to six hours. (He started with two hours but I flatly disbelieved it.) We also came back to the idea of a polymath project devoted to Frankl’s conjecture.

This is not the only TAU combinatorics seminar. Two days later, on May 2 Patrick Morris gave a special seminar about a robust Corrádi–Hajnal Theorem (joint work with Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Matthew Jenssen, Barnaby Roberts and Jozef Skokan.) As far as I know there are plans to have special seminars dedicated to both the new ultimate Roth bounds and the Ramsey breakthrough.

Of course, there is also the weekly discrete and computational geometry seminar, and a few weeks ago I gave a talk about “covering problems” which was well accepted and is in line with this year’s theme for the seminar.

More combinatorics seminars

There are many other combinatorics seminars around. If you have an urge for combinatorics lectures between the Tel Aviv seminar and the one in Jerusalem, on Sundays at 2 o’clock there is the Bar Ilan weekly Combinatorics Seminar, and on May 7 Yelena Yuditsky talked about Conflict-free colouring of subsets (joint work with Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.) On Mondays Martin Golumbic runs the seminar: “Monday with Marty and Students of Sunil” devoted to algorithmic graph theory. Tomorrow, Pradeesha Ashok talks about: Exact and Parameterised algorithms for Graph Burning (joint work with Avi Tomar, Shaily Verma, Sayani Das, Lawqueen Kanesh and Saket Saurabh).

Shmuel Weinberger’s lectures

Of course, things are just as amazingly intense in other fields of mathematics as well. Last week I attended two great talks by Shmuel Weinberger. The first talk gave the answer to the question which groups act without fixed points on some aspherical topological space. Shmuel said that his talk will be structured like a Tarantino’s movie, and at the end he expressed hope that the talk was as entertaining but not as violent. This is based on joint work with Sylvain Cappell, and Min Yan. The second talk gave (among other things) an exponential lower bound for the number of vertices needed to triangulate $n$ -dimensional lens spaces. The proof goes via the notions of $\ell_2$ -homology and certain invariants of Cheeger and Gromov and it would be really nice to have some simpler proofs. (This is based on an old work with Stanley Chang, and a new work with Geunho Lim.

Here is a lecture on calculus on extraordinary spaces by Yael Karshon (Hebrew).

Kazhdan’s Sunday seminars – a plan for fall 2024 (maybe 2023).

Since David Kazhdan moved from Harvard to HUJI he is running four-five semester-long seminars every year on Sundays, and a basic notion seminar on Thursday afternoons. This semester, for example, in one of the seminars, Udi de Shalit presents Wiles’ proof of Fermat’s last theorem (taking Ribet’s part for granted).

Once every decade or so, I serve as a co-teacher in a Kazhdan seminar. In fall 2003 David Kazhdan and I ran a seminar on polytopes, toric varieties, and related combinatorics and algebra. In 2013 David and I felt that it was time to run another such event in 2014, perhaps establishing a tradition for a decennial joint seminar. I announced this coming event in my January 2013 post and wrote: “So next spring, the plan is …[to] devote one of David’s Sunday seminars to computation, quantumness, symplectic geometry, and information.” Alas, David had a terrible car accident and we had to delay the plan to a fall 2019 seminar that Leonid Polterovich, Dorit Aharonov, Guy Kindler and I ran. Also, in fall 2018, Karim Adiprasito gave a Kazhdan seminar on “Positivity in combinatorics and beyond” where Karim presented his proof for the g-conjecture. We are now planning a Kazhdan seminar in fall 2024 around “global hypercontractivity” with Noam Lifshitz, myself and perhaps also Guy Kindler and others. (Kazhdan’s 2023/2024 schedule was fully booked, but come to think of it, since Dor Minzer is in town in fall 2023, maybe we will do something then.)

60th birthday conferences for the young: Gunter Ziegler and Leonid Polterovich

Noga Alon recently complained that “younger and younger people are celebrating their 60th birthdays”. Indeed, two weeks from now there will be a day-and-a half workshop in Berlin celebrating Günter Ziegler’s birthday and in June there will be a Leonid Polterovich fest in Zurich. Happy birthdays, kids!

Maybe it is over

A well-known Israeli poet and writer Yonatan Gefen passed away recently and here is a nice song he wrote (performed by Arik Einstein): Yhachol lihyot sheze nigmar (It is possible that it is over.)