## An Interview with Yisrael (Robert) Aumann

I was privileged to join Menachem Yaari and Sergiu Hart in interviewing Yisrael Aumann.  The interview is in Hebrew. It is an initiative of the Israel Academy of Sciences and the Humanities.

For our non Hebrew speakers here is in English an interview with Aumann by Sergiu Hart from 2005, and here is a paper  that I wrote in 2006  Science, beliefs and knowledge: a personal reflection on Robert J. Aumann’s approach.

Aumann explained to us some details of his Ph D thesis on knot theory,

Can game theory help resolving human conflicts and the suffering and waste caused by them?

Entomologist observe ants but dont tell them what to do.

Posted in Academics, Combinatorics, Games, Geometry, Rationality | | 1 Comment

## Igor Pak is Giving the 2018 Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

### Update: The lectures this week are cancelled.  They will be given at a later date.

Next week Igor Pak will give the 2018 Erdős Lectures

## Combinatorics — Erdos lecture: Igor Pak (UCLA) “Counting linear extensions”

11:00am to 12:30pm

## Location:

IIAS, Eilat hall, Feldman bldg (top floor), Givat Ram
I will survey various known and recent results on counting the number of linear extensions of finite posets. I will emphasize the asymptotic and complexity aspects for special families, where the problem is especially elegant yet remains #P-complete.

## CS Theory — Erdős Lecture: Igor Pak (UCLA) “Counting Young tableaux”

Igor Pak (UCLA)
10:30am to 12:00pm

## Location:

Rothberg (CS building) B-220

The number of standard Young tableaux of skew shape is a mesmerizing special case of the number of linear extensions of posets, that is important for applications in representation theory and algebraic geometry.  In this case there is a determinant formula, but finding their asymptotics is a difficult challenge.  I will survey some of the many beautiful result on the subject, explain some surprising product formulas, connections to Selberg integral, lozenge tilings and certain particle systems.

## Colloquium: Erdos lecture – Igor Pak (UCLA) “Counting integer points in polytopes”

2:30pm to 3:30pm

## Location:

Manchester Building (Hall 2), Hebrew University Jerusalem
Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From a computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc.?

## Vera T. Sòs, Doctor Philisophiae Honoris Causa, Hebrew University of Jerusalem

Videotaped by Ehud Friedgut.

## Sailing into High Dimensions

On June 20 at 13:30 I talk here at HUJI about Sailing into high dimensions. (Thanks to Smadar Bergman for the poster.)

Posted in Combinatorics, Geometry, Updates | Tagged | 1 Comment

## Conference in Singapore, Vietnam, Appeasement, Restorative Justice, Laws of History, and Neutrinos

Eliezer Rabinovici

Some weeks ago I returned from a beautiful trip to Singapore and Vietnam. For both me and my wife this was the first trip to these very interesting countries. In Singapore I took part in a very unusual scientific meeting Laws: Rigidity and Dynamics, and my old-time friend Eliezer Rabinovici was one of the organizers. Eliezer, a prominent theoretical physicist,  was the force behind SESAME, a unique scientific endeavor cospnsored  by Jordan-Iran-Israel-Pakistan-Egypt-Cyprus-The Palestinian authority-Turkey which we previously mentioned in this post.  There is something amazing about a scientific project in Jordan sponsored jointly by Israel and Iran with the involvment of Turkey, Egypt, and Pakistan.

(Some background for readers unfamiliar with the situation in the Middle East: these days, as in the last decades, and even more so than before, there is some hostility and tension between Israel and Iran.)

Eliezer was also the main force behind Isreal joining CERN where he served as a vice-president. As having interest in both  theoretical aspect of soccer, and in actually playing, I was especially amazed by the festive soccer game organized by Eliezer between the two top Israeli teams, which included, in the break, a historic game between the HUJI soccer team and the team of the Knesset, the Israeli parliament.  (Our team won big-time.)

Not everyone shares my excitement about SESAME. What do you think?

Singapore’s  investments in education, science, art, and public housing are impressive

(Compare the sculpture with this picture. )

## Darkest hours and appeasement

On the flight to Singapore I saw the excellent film “darkest hours” about the early weeks of World War II and Winston Churchill’s  early days as prime minister. Also in the guided tours in Singapore a lot of attention was given to the surrender of Singapore and the war memories, and needless to say that the memory of war was very much present while we were traveling in Vietnam. The Churchill movie was truly excellent, bringing us back to the appeasement policy of the two prime ministers before him, and the tragic and disastrous pursuit  of peace. I was wondering if the great military weakness of England (and France) in 1939 was a logical consequence of the appeasement policy/philosophy. Can you have a combined policy of strength and appeasement? Is appeasement ever justified?

## Laws and predictions in History

The conference I took part in in Singapore was the  3rd UBIAS Intercontinental Academia (ICA) – Laws: Rigidity and Dynamics, In short, it was a conference about “laws”. (The first conference of this kind was about “time” and the second about “human dignity”.) There were altogether 16 exciting mentors and 18 brilliant fellows from all areas of academia.

Nobel laureate  physicist David Gross was one of the mentors. (Ada Yonath was another mentor, but she arrived shortly before I left.) Both David Gross and Eliezer Rabinovici were pushing for some sort of physics-style laws or at least physics-style scientific exploration in History. I am quite skeptical about this idea and it even took me some time to realize that David and Eliezer were serious about it. (I suppose that the chaotic nature of historical developments is one good reason for skepticism.) Davis Gross (whom I found to be rather nice on a personal level) self-described  his view on academia and science as “arrogant” and his bold and provocative statements provided much food for thought and discussion throughout the conference. Anyway, when it comes to history, IAS historian  Patrick Geary gave quite an appealing argument for what we can expect and what we cannot expect from historical laws, with some very interesting examples.

Penelope (Penny) Andrews

## The afternoon session of March 20

### Constitution and Love – The South African constitution and restorative justice

Penelope (Penny) Andrews who had just arrived after a 24 hours flight from Cape Town gave a beautiful (and moving) talk entitled “The ‘casserole’ constitution – South African constitution and international law”. The talk was about the creation of South African human-rights based constitution,  and the struggle of South African democracy afterwards.  I strongly recommend watching the lecture. I was scheduled to be one of the responders.

What do I have to contribute to a discussion on the South African constitution? I had one personal story to tell: My father’s parents left from Lithuania for Israel (or Palestine as it was called under the British rule) in 1923 and my grandmother’s brother Hirsch stayed there.  During WWII  Hirsch’s daughter (my father’s cousin) Dora Love (Rabinowitz) was moved from one concentration camp to another, and lost her sister and her mother in the Nazi camps. After the war she met and married an English soldier Frank Love and they both moved to South Africa. Dora was a teacher at a Hebrew school in Johannesburg (among her students were Peter and Neil Sarnak), and also spent much of her life lecturing about the Holocaust. Her younger daughter Janet Love joined Mandela’s ANC at a young age, was considered a “terrorist” for more than a decade and had to flee South Africa. She eventually returned to South Africa and actually took part in the negotiations for the new constitution. After that she served in the South African parliament for five years and later on several governmental posts, now serving as the South Africa Human Rights Commissioner. (This story took Penny Andrews by surprise and it turned out she knows Janet well.)

Besides that I prepared one comment on the issue.  My comment/question/suggestion was about applying South Africas’s famous Truth and Reconciliation policy  in the criminal law. Can we apply similar principles there? I was especially thinking about the situation regarding sexual harassments and other sexual crimes which seem to be very wide spread. Here, as in other aspects of criminal law, it is not clear at all whether the instinctive demand for harsher punishments is correct. Restorative justice seems of relevance. (I suppose this is also an appeasing approach of some sort.)  Penny Andrews gave a very thoughtful answer including on cases in SA and elsewhere where a restorative system of justice is implemented.

Janet Love (right). The Love family visited Israel in the late 60s (and brought me my first jacket). On the left is Seth, Janet’s older brother.  (I added more pictures at the end of the post.)

### My talk

My own talk was about quantum computing. Given the wide interests of the audience I promised to be non technical and to have less mathematics in my talk compared to the talk about history by Patrick Geary. It is a good time to revisit this issue here on the blog but let me delay it to another post. David Gross asked me if I really thought that my hand-waving computer-science argument against quantum computers applies to show infeasibility of structures that serious physicists had given much thought to.  (He mainly referred to topological quantum computing.) My answer was “yes”.

Atul Parikh did a brilliant job in responding to me. Here is a link to a video of this session. For another session with two great talks by Atul Parikh and Ada Yonath see this video. A session with Michal Feldman’s conference-opening talk and Patrick Geary’s talk is here. A session with talks by Partha Dasgupta and David Gross is here. Combinatorialists may  enjoy the introduction by Robin Mason to Frank Ramsey at the beginning. (Have a look also at David and others’ response t0 Partha’s talk and Partha’s rejoiner.)  The entire collection of videotaped sessions is here. There are many interesting talks and discussions.

## Sights from Vietnam

Mathematicians’  lunch at Hanoi. From right Phan Ha Duong, me, Ngo Viet Trung, Nguyen Viet Dung, and Le Tuan Hoa. Below: Halong Bay

Janet Love, Frank Love, Seth Love, Tami Kalai (my sister), Dora Love, Hanoch Kalai (my father), near our home in Jerusalem. Below, a few years later with the jacket.

## Two dimensions

Before we talk about 4 dimensions let us recall some basic facts about 2 dimensions:

### A planar polygon has the same number of vertices and edges.

This fact, which just asserts that the Euler characteristic of $S^1$ is zero, can be reformulated as: Polygons and their duals have the same number of vertices.

A linear algebra statement

The  spaces of affine dependencies of the vertices  for a polygon P and its dual P* have the same dimension.

I am not aware of a pairing or an isomorphism for demonstrating this equality. (See, however Tom Braden’s comment.)

## Four dimensions

Given a 4-dimensional polytope P define $\gamma (P) =f_1(P) + f_{02}(P)-3f_2(P)-4f_0+10.$

Here, $f_i(P)$ is the number of $i$-faces of $P$. $f_{02}(P)$ is the number of chains of the form 0-face $\subset$ 2-face. In other words it is the sum over all 2-faces of P, of the number of their vertices. In 1987 I discovered the following:

Theorem [Mysterious Four-dimensional Duality]: Let P and P* be dual four dimensional polytopes then

### (1)   γ(P)=γ(P*)

Here is an example: Let $P$ be the four dimensional cube. In this case $f_0=16$, $f_1=32$, $f_2=24$, $f_3=8$, and since every 2-face has 4 vertices $f_{02}=96$. $\gamma (P)=32+96-72-80+10=2$. $P^*$ is the 4-dimensional cross-polytope with  $f_0=8$, $f_1=24$, $f_2=32$, $f_3=16$, and since every 2-face has 3 vertices $f_{02}=96$$\gamma (P^*)=24+96-96-40+10=2$. Viola!

The proof of (1) is quite a simple consequence of Euler’s theorem.

For the 120-cell and its dual the 600-cell $\gamma=250$.

## Frameworks, rigidity and Alexandrov-Whiteley’s theorem.

A framework based on a $d$-polytope $P$ is obtained from $P$ by adding diagonals which triangulate every 2-face of $P$. Adding the diagonals leads to an infinitesimally rigid framework. This was proved by Alexandrov for 3 dimension and by Walter Whiteley in higher dimensions.

Walter Whiteley

Theorem (Alexandrov-Whiteley): For $d\ge 3$, every famework based on $P$ is infinitesimmaly rigid.

It follows from the Alexandrov-Whiteley theorem that for a four-dimensional polytope $P$, $\gamma (P)$ is the dimension of the space of stresses of every  framework based on $P$. (An affine stress is an assignment of weights to edges so that every vertex lies in “equilibrium”.) Whiteley’s theorem implies that $\gamma (P) \ge 0$ for every 4-dimensional polytope $P$.

4-dimensional stress-duality: Let P and P* be dual four dimensional polytopes. Then the space of affine stresses for a frameworks based on P and on P* have the same dimension.

Again, I am not aware of a pairing or an isomorphism that demonstrates this equality between dimensions. (See, however Tom Braden’s comment.)

Remark: Given a $d-$polytope $P$,  let $f_1^+(P)$ be the number of edges in a framework based on $P$. We can define for every $d$-polytope, $\gamma (P)=f_1^+(P)-df_0(P)+{{d+1} \choose {2}}$. Whiteley’s theorem implies that $\gamma (P) \ge 0$ for every $P$. (For $d=3$ by Euler’s theorem $\gamma =0$.)

Just as a polytope in dimension greater than 2 need not have the same number of vertices as its dual, it is also no longer true in dimensions greater than 4 that $\gamma(P)$ equals $\gamma (P^*)$. However, it is true in every dimension that $\gamma (P)=0$ if and only if $\gamma (P^*)=0$.

## Toric varieties

Let $T(P)$ be a toric variety based on a rational 4-dimensional polytope $P$. The dimension of the primitive part of the 4th intersection homology group of $T(P)$ is equal to $\gamma (P)$.  Our duality theorem thus asserts that the primitive part of the 4th intersection homology group of $T(P)$ has the same dimension as the primitive part of the 4th intersection homology group of $T(P^*)$.

Some references: Whiteley’s theorem (Whiteley, 1984); The 4-d duality relation (Kalai, 1987);  A more general relation (Bayer and Klapper, 1991); An even more general relation (Stanley; 1992) Related theorems on combinatorics of polytopes (Braden, 2006);  Connection to Mirror symmetry (Batyrev and Borisov, 1995); Connection to Koszul duality (Braden, 2007); Rigidity and polarity in 3-d (Whiteley 1987)

Posted in Combinatorics, Convex polytopes | Tagged | 4 Comments

## Duncan Dauvergne and Bálint Virág Settled the Random Sorting Networks Conjectures

A short summary: The beautiful decade-old conjectures on random sorting networks by  Omer Angel, Alexander Holroyd, Dan Romik, and Bálint Virág, have now been settled by Duncan Dauvergne and Bálint Virág in two papers: Circular support in random sorting networks, by Dauvergne and Virág, and The Archimedean limit of random sorting networks by Duncan Dauvergne.

Dan Romik, see also Romik’s mathematical gallery and Romik’s moving sofa page

## Sorting networks

Sorting is one of the most important algorithmic tasks and it is closely related to much beautiful mathematics. In this post, a sorting network is a shortest path from 12…n to n…21 in the Cayley graph of S_n generated by nearest-neighbour swaps. In other words, a sorting networks is a sequence of ${{n} \choose {2}}$ transpositions of the form $(i,i+1)$ whose product is the permutation $(n,n-1,\dots,1)$.

Sorting networks, as we just defined,  appear in other contexts and under other names. Also  the term “sorting networks” is sometimes used in a different way, and in particular, allows swaps that are not nearest neighbors. (See the slides for Uri Zwick’s lecture on sorting networks.)

Richard Stanley proved a remarkable formula

${{n}\choose{2}}!/1^n3^{n-1}5^{n-2}\cdots (2n-3)^1,$

for the number of sorting networks or reduced decomposition of the permutation n…21.  (We mentioned it in this post. )

We can also think about sorting networks as  maximal chains in the weak Bruhat order of the symmetric group.  Another related notion in combinatorial geometry is that of  “(simple) allowable sequence of permutations”. an allowable sequence of permutation is a sequence of permutations $\pi_1,\pi_2,\pi_t$ starting with  12…n and ending with n…21 such that each permotation in the sequence is obtained by the previous one by reverseing one set or several disjoint sets of consecutive elements. See, e.g., this paper of Hagit last on two proofs of the Sylvester-Gallai theorem via allowable sequence of permutations.

## Random Sorting networks

Alexander Holroyd’s videotaped lecture on random sorting networks. Holroyd’s random sorting gallery (pictures below are taken from there), and his six other amazing mathematical gallerys

Random sorting networks were considered a decade ago in a beautiful paper by Angel, Holroyd, Romik, and Virág . In this paper some brave conjectures were made

Conjecture 1: the trajectories of individual particles converge to random sine curves,

Conjecture 2:  the permutation matrix at half-time converges to the projected surface measure of the 2-sphere.

There are more conjectures! I will just show you one additional picture

The rhombic tiling corresponding to a uniform random sorting network:

## The works by Dauvergne and Virág

In two recent breakthrough papers all those conjectures were proved. The papers are

1. Circular support in random sorting networks, by Dauvergne and Virag

…in which they show the tight support bound for the circle seen in the halfway permutation, as well as the tight Lipschitz bound for trajectories.

2. The Archimedean limit of random sorting networks, by Dauvergne.

…in which all the 2007 conjectures are proved. Here is the abstract:

A sorting network (also known as a reduced decomposition of the reverse permutation), is a shortest path from 12⋯n to n⋯21 in the Cayley graph of the symmetric group Sn generated by adjacent transpositions. We prove that in a uniform random n-element sorting network $\sigma^n$, that all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-t permutation matrix measures of $\sigma^n$. As a corollary of these results, we show that if $S_n$ is embedded into $\mathbb R^n$ via the map τ↦(τ(1),τ(2),…τ(n)), then with high probability, the path σn is close to a great circle on a particular (n−2)-dimensional sphere in $\mathbb R^n$. These results prove conjectures of Angel, Holroyd, Romik, and Virag.

These papers build on previous results, including some in the 2007 paper, recent results by Gorin and Rahman from Random sorting networks: local statistics via random matrix laws, as well as those of Angel, Dauvergne, Holroyd and Virág from their paper on the local limit of random sorting networks.

## The halving (pseudo)lines problem

Let me mention an important conjecture on sorting networks,

Conjecture: For every k, and $\epsilon >0$ the number of appearances of the transposition (k,k+1) in every sorting network is $O(n^{1+\epsilon})$.

This is closely related to the halving line problem. The best lower bound (Klawe, Paterson, and Pippenger) behaves like $n \exp (\sqrt {\log n})$. A geometric construction giving this bound  is a famous theorem by Geza Toth.   The best known upper bound by Tamal Dey is $n^{4/3}$.

I am amazed that I did not blog about the halving lines problem and about allowable sequences of permutations in the past. (I only briefly mentioned the problem and allowable sequences of permutations in one earlier post on a certain beautiful geometric discrepancy problem.)

## The permutahedron makes an appearance

The permutahedron is the Cayley graph of the symmetric group Sn generated by the nearest-neighbour swaps (12)(23)(34) and (n-1n). (Here $n=5$.) Are there analogous phenomena for the associahedron? one can ask.

## Zur Luria on the n-Queens Problem

(From Wikipedia )

The eight queens puzzle is the famous problem of placing eight chess queens on a chessboard so that no two queens threaten each other. The questions if this can be done and  in how many different ways, as well as the extension to n queens on a n × n chessboard  was raised already in the mid nineteen century.  Apparently Gauss was interested in the problem and figured out that the number of solutions for the 8 × 8  board is 92, and  Zur Luria gave a beautiful lecture about  his new results on the number of solutions in our seminar earlier this week. The lecture follows Luria’s paper New bounds on the n-queens’s problem.

Before getting to Zur’s result a little more on the history taken from Wikipedia: “Chess composer Max Bezzel published the eight queens puzzle in 1848. Franz Nauck published the first solutions in 1850. Nauck also extended the puzzle to the n queens problem, with n queens on a chessboard of n × n squares. Since then, many mathematicians, including Carl Friedrich Gauss, have worked on both the eight queens puzzle and its generalized n-queens version. In 1874, S. Gunther proposed a method using determinants to find solutions… In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming. He published a highly detailed description of a depth-first backtracking algorithm.” For more on the history and the problem itself see the 2009 survey by Bell and Stevens.  Let me also mention the American Mathematical Monthly paper The n-queens problem by Igor Rivin, Ilan Vardi and Paul Zimermmann.  (In preparing this post I realized that there are many papers written on the problem.)

Let $Q(n)$ be the number of ways to place n non attacking queens on an n by n board, and let $T(n)$ be the number of ways to place n non-attacking queens on an n by n toroidal board.  $Q(n)$ is sequence A000170 in the On-Line Encyclopedia of Integer Sequences.  The toroidal case, also referred to as the modular n-queens problem was asked by Polya in 1918. Polya proved that $T(n) \ne 0$ iff $n$ is 1 or 5 modulo 6. (Clearly, $T(n) \le Q(n) \le n!$.)

Here are Zur Luria’s new results:

Theorem 1: $T(n) = O(n^n/e^{3n})$

Theorem 2: $Q(n) = O(n^n/e^{\alpha n})$, for some $\alpha >1$.

As far as I know, these are the first non-trivial upper bounds.

Theorem 3: For some constant $c>0$, if $n$ is of the form $2^{2k+1}+1$ then $T(n) \ge n^{cn}$.

Update: In the lecture Zur noted that the proof actually works for all odd n such that -1 is a quadratic residue mod n.

Theorem 3 proves (for infinitly many integers) a conjecture by Rivin, Vardi, and Zimmermann, who proved exponential lower bounds. Luria’s beautiful proof can be seen (and this is how Zur Luria views it) as a simple example of the method of algebraic absorbers, and Zur mentions  an earler application of a similar methods is in a paper of Potapov on counting Latin hypercubes and related objects.  Rivin, Vardi and Zimmermann conjectured that the exponential generating function of $T(n)$ has a closed form and understanding this generating function is a very interesting problem. Luria conjectures that his upper bound for $T(n)$ is sharp.

Luria’s conjecture: $T(n) = n^n/e^{3n (1+o(1))}$.

In view of recent progress in constructing and counting combinatorial designs this conjecture may be within reach. Zur also conjectures that for $Q(n)$, 3 should be replaced by some $\beta<3$.

More on chess on this blog: Chess can be a Game of Luck,  Amir Ban on Deep Junior, and quite a few other posts.

Posted in Combinatorics, Games | | 6 Comments

## Testing *My* Intuition (34): Tiling High Dimension with an Arbitrary Low-Dimensional Tile.

A tile $T$ is a finite subset of $\mathbb Z^d$. We can ask if $\mathbb Z^d$ can or cannot be partitioned into copies of $T$. If  $\mathbb Z^d$ can be partitioned into copies of $T$ we say that $T$ tiles $\mathbb Z^d$.

Here is a simpe example. Let $T$ consists of 24 points of the 5 by 5 planar grid minus the center point. $T$ cannot tile $\mathbb Z^2$.

Test your intuition: Does $T$ tiles $\mathbb Z^d$ for some $d>2$?

We had a poll and 58% of voters said YES. The answer is

## My Copy of Branko Grünbaum’s Convex Polytopes

Branko Grünbaum is my academic grandfather (see this highly entertaining post for a picture representing five academic generations). Gunter Ziegler just wrote a beautiful article in the Notices of the AMS on Branko Grunbaum’s  classic book “Convex Polytopes”, so this is an opportunity to tell the story of my copy. The book was written with the cooperation of Victor Klee, Micha Perles (my Ph. D supervisor) and Geoffrey Shephard. Since the late 70s the book was out of print and it was extremely difficult to get a copy.

In 1983 I was a postdoc in MIT and there was a lovely group of young combinatorialists around. At MIT, Noga Alon, and I, as well as  Ian Goulden and a few others were postdocs,  Jeff Kahn, Paul Seymour, Ira Gessel, and Anders Björner were junior faculty, Gunter Ziegler, Mark Haiman, Francesco Brenti, and Peter Shor were among the graduate students. There were many computer scientists with interest in combinatorics and at Northeastern there were two young faculty members, Marge Bayer and Dom (Dominique) de Caen working in combinatorics, and an algebraic geometer Jonathan Fine who also became interested in combinatorics.

One day, Dom de Caen saw me and told me that some months earlier he had managed to find a copy of “Convex polytopes” in a used book store and bought it for 10 dollars. He said that he knew how rare the book was and how hard it was to get it, but decided to give it to me  since I would make  better use of it working in this special area.

In 2003, after several years of work, a second edition was published which contained the original text and some additional material prepared by a fresh team of young researchers: Volker Kaibel, Victor Klee, and Gunter Ziegler. This was really great. I bought a copy and had the idea to send it to Dom as a form of gratitude for his previous gesture of kindness.  So I tried to find his address over the Internet. I was sad to learn that Dom had passed away in 2002. You can read about Dom’s mathematics in this paper by  Edwin R. Van Dam,  The combinatorics of Dom de Caen.

Posted in Combinatorics, Convex polytopes, Nostalgia | | 3 Comments