## 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 | 5 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 | | 7 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

## Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations

The high-dimensional conference in Jerusalem is running with many exciting talks (and they are videotaped), and today in Tel Aviv there is a conference on Optimization and Discrete Geometry : Theory and Practice.

Today in Jerusalem, Leonard Schulman talked (video available!) about a  recent breakthrough by  Gil Cohen, Bernhard Haeupler, and Leonard Schulman in the recent paper Explicit Binary Tree Codes with Polylogarithmic Size Alphabet.

## Tree codes

Tree codes are extremely important objects invented by Leonard Schulman in 1992-1996. You can read about it in Wigderson’s book  Mathematics and Computation  (see also this post) in a whole section about  Error-correction of interactive communication, a theory pioneered by Leonard. Finding explicit good (linear distance, finite alphabet) tree codes is a very important problem.

(From the introduction of the new paper) “A tree code consists of a complete rooted binary tree (either infinite or of finite depth $n$) in which each edge is labeled by a symbol from an alphabet $\Sigma$ . There is a natural one-to-one mapping assigning each binary string $s$ to a path starting at the root, where $s$ simply indicates which child is taken in each of the steps. For a tree code, such a path naturally maps to a string over the alphabet $\Sigma$, which is formed by concatenating the symbols along the path. This way a tree code $T$ encodes any binary string $s$ into an equally long string $T(s)$ over $\Sigma$. This encoding has an online characteristic because the encoding of any prefix does not depend on later symbols. In particular, any two distinct strings that agree in their first $k$ symbols also have encodings that agree in their first $k$ symbols. A tree code is said to achieve distance  $\delta \ge 0$ if the encodings of any two strings differ in at least a $\delta$-fraction of the positions after their first disagreement. The rate of a tree code is $1/\log _2 (\Sigma )$. A tree code is said to be asymptotically good if it achieves both constant distance $\delta >0$  and a constant rate, namely, the alphabet size is $O(1)$.”

### The abstract:

“This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant 1 we give an explicit binary tree code with distance  and alphabet size $(\log n)^{O(1)}$, where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size $n^{O(1)}$.

As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis – a result of independent interest.”

### Problems on Exponential sums

A few years ago Cris Moore and Leonard Schulman proposed an explicit constructions for good tree codes in the paper Tree codes and a conjecture on exponential sums. The construction depends on still open conjectures on new types of exponential sums.

## A paper by Leonard and me on polynomials with massive cancellations.

So let me use this opportunity to advertize a paper by Leonard and me Quasi-random multilinear polynomials which was just accepted for publication in the Israel Journal of Mathematics. Unexpected cancellation is always a very interesting phenomenon that we cherish and wish to understand. For example, we expect that the sum of the Mobius function for the first n integers cancels almost like that of a random walk. Depending on the meaning of “almost” this is the (known) prime number theorem, the (conjectured) Riemann hypothesis, or simply false, respectively.

A little less famous example  (which I personally like) is the paper by Nikola Djokic  an upper bound on the sum of signs of permutations with a condition on their prefix sets solving a problem by J. Feldman, H. Knorrer, and E. Trubowitz.

Our starting point is the determinant: It is a polynomial of degree $n$ of $n^2$ variables and no matter what $\pm 1$ values you assign to the variables you have a massive cancellation of almost a random-walk type. There are $n!$ terms and for any assignment the value is smaller than $n^{n/2}$ which is $(n!)^{1/2+o(1)}$.  We were interested in the question of finding other such polynomials.

## Test Your Intuition (34): Tiling high dimensional spaces with two-dimensional tiles.

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$?

If you prefer you can think about the simpler case of $T_0$ consisting of eight points: the 3 by 3 grid minus the center.

## Coloring Problems for Arrangements of Circles (and Pseudocircles)

To supplement and celebrate Aubrey de Grey’s result here are

## Eight problems on coloring circles

A) Consider a finite family of unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

This is the question about the chromatic number of the plane. (Or the maximum chromatic number of planar unit-distance graphs.) By the Aubrey de Grey’s result the answer is 5, 6, or 7.

B) Consider a finite family of non-overlapping unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Now we talk about planar unit-distance graphs where the distance between every pair of points is at least one. Those are also called Penny graphs. The answer is four.

C) Consider a finite family of pairwise intersecting unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors? Continue reading

Posted in Combinatorics, Geometry, Open problems | | 8 Comments

## Aubrey de Grey: The chromatic number of the plane is at least 5

A major progress on an old standing beautiful problem. Aubrey de Grey proved that the chromatic number of the plane is at least 5. (I first heard about it from Alon Amit.)

The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is referred to as the chromatic number of the plane. The problem was posed in 1950 by Edward Nelson, and related results already appeared in a paper by Hugo Hadwiger from 1945. Untill recently it was known that the answer can be 4,5,6 or 7. The Moser spindle is a simple example of a unit-distance graph with chromatic number 4, and there is a simple coloring of the plane, found by Isbell, based on the hexagonal packing with 7 colors so that no color contains a pair of points of distance 1.

Updates: Aubrey de Grey has made now a polymath proposal over the polymath blog aimed at finding simpler constructions, namely constructions with a smaller number of vertices, or where the computerized part of the proof is simpler. Of course, this project may lead to independent verification of the result, and perhaps even insights for what is needed to replace ‘5’ with ‘6’. Noam Elkies independently proposed over MathOverflow a polymath project following Aubrey de Grey’s paper. (April 14) Dustin Mixon and Aubrey de Grey have launched Polymath16 over at Dustin’s blog. The project is devoted to the chromatic number of the plane (Wikipage) following Aubrey de Grey’s example showing that the chromatic number of the plane is at least 5.

Here is an earlier Google+ post by Terry Tao and an earlier blogpost on the new result by Jordan Ellenberg proposing to use the polynomial method to tackle the upper bound. A blog post reporting on independent verification of some of the new results is over Dustin G. Mixon’s blog  Short, Fat Matrices. A post over Shtetl Optimized describes the new development along with another important development on quantum computation. Let me also mention two related old posts over Lipton and Regan’s blog (one, two). (April 19) An excellent article on Quanta Magazine by Evelyn Lamb. (April 21) A great blog post (French) on Automath.

(From Wikipedea: A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane (the Moser spindle), providing upper and lower bounds for the Hadwiger–Nelson problem.) Below, two figures from Aubret de Grey’s paper.

Let me also mention the related Rosenfeld’s problem discussed in this post: Let G be the graph whose vertices are points in the plane and two vertices form an edge if their distance is an odd integer. Is the chromatic number of this graph finite?

These and related problems are discussed also in my survey article: Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

## Conference on High Dimensional Combinatorics

Conference home-page