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

Posted in Combinatorics, Probability, Updates | | 1 Comment

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

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

## Speakers include:

 David Conlon University of Oxford Michael Farber Queen Mary, University of London Howard Garland* Yale University Lev Glebsky Universidad Autónoma de San Luis Potosí Misha Gromov* IHES Venkatesan Guruswami Carnegie Mellon University Ming-Hsuan Kang National Chiao Tung University Daniela Kühn University of Birmingham James Lee University of Washington Winnie Li Pennsylvania State University Shachar Lovett UC San Diego Roy Meshulam Technion Deryk Osthus University of Birmingham János Pach NYU Peter Sarnak IAS, Princeton Leonard Schulman Caltech Uli Wagner IST Shmuel Weinberger University of Chicago Avi Wigderson IAS, Princeton Gilles Zémor Université de Bordeaux

## Nathan Rubin Improved the Bound for Planar Weak ε-Nets and Other News From Ein-Gedi

I just came back from a splendid visit to Singapore and Vietnam and I will write about it later. While I was away, Nathan Rubin organized a lovely conference on topics closed to my heart  ERC Workshop: Geometric Transversals and Epsilon-Nets with many interesting lectures. Nathan himself announced a great result with new upper bounds for planar weak ε-nets. In 2007 I wrote a guest post (my first ever blog post) on the topic on Terry Tao’s blog. The next section is taken from that old post with reference to one additional result from 2008.

## Weak ε-Nets

### Definition: Let $X \subset {\Bbb R}^d$ be a finite set of points, and let $0 < \epsilon < 1$. We say that a finite set $Y \subset {\Bbb R}^d$ is a weak $\epsilon$-net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that $|B \cap X| > \epsilon |X|$, then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong $\epsilon$-net for X with respect to convex bodies.)

let $f(\epsilon,d)$ be the least number such that every finite set X possesses at least one weak $\epsilon$-net for X with respect to convex bodies of cardinality at most $f(\epsilon,d)$. (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from covering more than $\epsilon$ of any given territory.

A central problem in discrete geometry is:

Problem: For fixed d, what is the correct rate of growth of f as $\epsilon \to 0$?

It is already non-trivial (and somewhat surprising) that $f(\epsilon,d)$ is even finite. This fact was first shown by Alon, Bárány, Füredi, and Kleitman (the planar case was achieved earlier by Bárány, Füredi, and Lovász), who established a bound of the form $f(\epsilon,d) = O_d( 1/\epsilon^{d+1})$; this was later improved to $O_d(\frac{1}{\epsilon^d} \log^{O_d(1)} \frac{1}{\epsilon} )$ by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl. In the other direction, the best lower bound was for many years $c(d)/\epsilon$ for some positive c(d); it was shown by Matousek that c(d) grows at least as fast as $e^{c\sqrt{d}}$for some absolute constant c. In 2008 Bukh, Matousek, and Nivasch proved  that $f(\epsilon,d) \ge (1/\epsilon) (\log (1/ \epsilon)^{d-1}$.

## Nathan Rubin’s new theorem

In the plane the state of our knowledge was that (up to constants) for every $\delta >0$) $(1/\epsilon )\log (1/\epsilon) \le f(2,\epsilon) \le (1/\epsilon)^{2+\delta}$. The new dramatic breakthrough is

Theorem (Nathan Rubin, 2018): $f(2,\epsilon) \le (1/\epsilon)^{3/2+\delta}$.

I hope the paper will be arxived in the next few months.

## Other results from Ein-Gedi

Here is a page with the titles and abstracts of the lectures. A lot of very interesting advancements on Helly-type theorems, transversals, geometric-Ramsey, topological methods and other topics. Let me briefly mention one direction.

## Improved (p,q)-theorems

Weak $\epsilon$-nets play an important role in the proof by Alon and Kleitman of the Hadwiger-Debrunner conjecture. The proof is so nice that I could not resist the temptation to present and discuss it in two comments (1,2) to my old 2007 posts.

Theorem (Alon and Kleitman): For every integers $p,q$ and $d$$p \ge q \ge d+1$, there is a function $M(p,q;d)$ such that the following is true:

Every finite family $\cal K$ of convex sets in ${\Bbb R}^d$ with the property that among every  $p$ sets in the family there are $q$ with non empty intersection can be divided to at most $M(p,q;d)$ intersecting subfamilies.

Dramatic improvements of the bounds for $M(p,q,d)$ were achieved in a 2015  paper Improved bounds on the Hadwiger-Debrunner numbers by Chaya Keler,  Shakhar Smorodinsky, and Gabor Tardos. This have led to further improvements and related results that Shakhar and Chaya talked about in the meeting.

## Other results around weak ε-Nets

There were various other developments regarding weak ε-Nets andrelated notions that occured since my 2007 post and the result of Buck, Matousek, and Nivasch in 2008, and probably I am not aware of all of them (or even forgot some). Of course, comments about related results are most welcome in the comment section. Here are links to a lecture by Noga Alon: 48 minutes on strong and weak epsilon nets (Part 1, Part 2). Let me mention just two beautiful recent developments: A paper On weak ε-nets and the Radon number by Moran and Yehudayoff  gives a simple proof for their finiteness in a very abstract setting. A paper by Har-Peled and Jones How to Net a Convex Shape studies interesting weaker notions. A weaker notion of weak epsilon nets is described in the work by Bukh and Nivash in Nivash’s Ein Gedi abstract.

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged | 1 Comment