Annotated Pictures from Fall 2024

Combinatorics and more 2025-01-26

Apart from pictures, I write about the very first “Test your Intuition” question, a pioneering work of Tutubalin, the hierarchy of valuations of Lehman, Lehman, and Nisan, and three conjectures of Miki Tarsi.

September 2024

Rothschild Symposium

From left to right: Nati Linial, Andrei Broder, me and Yosi Azar. (The Rothchild Symposium September.)

It was great to see Andrei after we did not meet in person for a couple of decades.

Both Andrei Broder and and Yosi Azar are mentioned in my 2007 post Test Your Intuition (1). Here is the question again:

Question: Suppose that we sequentially place $n$ balls into $n$ boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability $(1+o(1))\ln n/\ln \ln n$ balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. What will be the maximum occupancy?

Amichai Lampert, Hillel Furstenberg and Tammy Ziegler, Noam Lifshitz and me, Emmanuel Breuillard

Emmanuel Breuillard discussed central limit theorems for Heisenberg groups and more general nilpotent Lie groups, with a particular focus on his 2023 paper co-authored with Timothée Bénard. (I attached above his picture the definition of the Heisenberg group.) This fascinating area builds on the pioneering 1960 work of Valerii Nikolaevich Tutubalin, and the new paper answers a question posed by Tutubalin in the 1960s. Two decades ago, Emmanuel himself made significant progress in this field during his doctoral thesis, which is when we first met at Yale.

Shiri Ron gave a great lecture titled Strengthening truthfulness: Is it possible? (taken literally this is a very timely subject ). The slide on the right showcases a fascinating hierarchy of valuations (real functions over the discrete cube) introduced by Benny Lehman, Danny Lehman, and Noam Nisan in their 2002 paper Combinatorial Auctions with Decreasing Marginal Utilities. The class of real functions defined on the discrete cube (equivalently, on subsets of $\{1,2,,\dots, n\}$ ) plays a significant role in both optimization theory and game theory. An intriguing question would be to study the Fourier-Walsh expansions of functions within each class.

with Michael Ben-Or and Shafi Goldwasser

October 2024

Rosh Hashana and Sukkot

20241002_204106

Tel Aviv, Rosh Hashana, Lior and his nephew Yonatan

Jerusalem, Sukkot 2024, in the streets of my childhood.

Reichman University Memorial Exhibit

A visual memorial to the victims of October 7 at Reichman University

November 2024

wigder1

Amazing (?) coincidences! I first met Avi and Edna on the train to Jerusalem and when we left the train we also met my son Hagai.

Nati Linial, Avi Wigderson, Michal Linial, Miki Tarsi, me, Anita Tarsi, Yehuda Afek, and Edna Wigderson. (We met just before a lecture by Nati.)

And here are three long standing beautiful conjectures by Miki Tarsi and collaborators.

Alon-Tarsi conjecture (link: Wolfram mathword): A Latin $n \times n$ square is said to be odd if it contains an odd number of rows and columns that are odd permutations. Otherwise, it is said to be even. The Alon-Tarsi conjecture states that for even n, the number of even Latin squares differs from the number of odd Latin squares. This was proved by Drisco in 1988 when n is of the form $2^rp$ and p is a prime. (Here are slides of a nice lecture by Eric Moorhouse.)

Alon-Jaeger-Tarsi conjecture: For any (finite) field F with at least four elements and any non-singular matrix M over F there is a vector x such that both x and Mx have only non-zero entries. Here is a 2021 paper The Alon-Jaeger-Tarsi conjecture via group ring identities, by János Nagy and Péter Pál Pach where the conjecture is proved for fields of sufficiently large primes.

Jaeger- Linial- Payan-Tarsi conjecture: for any prime number p, there is a constant c such that for any n, the union (with repetition) of the vectors of any family of c linear bases of $\mathbb Z_p^n$ forms an additive basis of $\mathbb Z_p^n$ (i.e. any element of $\mathbb Z_p^n$ can be expressed as the sum of a subset of these vectors). Here is the paper by Jaeger-Linial-Payan-Tarsi and a paper by Alon-Linial-Meshulam where the conjecture is discussed.

About Miki Tarsi: In Summer 1978, we spent two weeks together at a summer school in combinatorics in Montreal. Among the speakers were Vera Sós, Richard Wilson, and Haim Hanani. While in Montreal, Miki wrote a fascinating children’s thriller about ants for his son Hagai.