Subspace Designs, Unit and Distinct Distances, and Piercing Standard Boxes.

A lot of things are happening and let me briefly report on three major advancements in combinatorics.

1. Peter Keevash, Ashwin Sah and Mehtaab Sawhney proved the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility conditions.  Here is the link to the paper: The existence of subspace designs.
2. Noga Alon, Matija Bucić, and Lisa Sauermann made an important advance on the study of unit distances and distinct distances in arbitrary normed space. Here is a link to the paper: Unit and distinct distances in typical norms. The unit distance and distinct distances problems for Euclidean geometry are old and famous, and much attention has been given to the question of what happens to these problems if one considers normed spaces other than the Euclidean plane. Alon, Bucić, and Sauermann give an essentially tight answer to both questions for almost all norms on , in a certain Baire categoric sense.
3. István Tomon’s paper: Lower bounds for piercing and coloring boxes. Here is Tomon’s abstract from his recent Copenhagen-Jerusalem seminar: Configurations of axis-parallel boxes in are extensively studied in combinatorial and computational geometry. Despite their innocent appearance, there are many old problems involving their structure that are still not well understood. I will talk about a construction, which addresses several of these problems, and shows that configurations of boxes may be more complex than people conjectured.

Subspace designs and q-analogs

We talked about subspace designs in this post  and in particular about the 2016 paper of Michael  Braun, Tuvi Etzion , Patric R. J. Östergard , Alexander Vardy,  and Alfred Wasserman. While preparing this post I learned the sad news that Alexander Vardy, a prominent coding theorist, had passed away a year ago at the young age of 58.

The theme of finding -analogs to combinatorial results and problems is important both in enumerative and algebraic combinatorics and in extremal combinatorics and it will be interesting to discuss it in some future post. While preparing for that I recalled the famous –Dyson conjecture that had been settled by Zeilberger and Bressoud in 1995. I learned that by now there are simpler proofs:  “A shorter proof, using formal Laurent series, was given in 2004 by Ira Gessel and Guoce Xin, and an even shorter proof, using a quantitative form, due to Karasev and Petrov, and independently to Lason, of Noga Alon’s Combinatorial Nullstellensatz, was given in 2012 by Gyula Karolyi and Zoltan Lorant Nagy. The latter method was extended, in 2013, by Shalosh B. Ekhad and Doron Zeilberger to derive explicit expressions of any specific coefficient.” (Wikipedia.)

Unit and distinct distances

Here is the abstract of the paper by Alon, Bucić, and Sauermann:

Erdős’ unit distance problem and Erdős’ distinct distances problem are among the most classical and well-known open problems in all of discrete mathematics. They ask for the maximum number of unit distances, or the minimum number of distinct distances, respectively, determined by $latex n$ points in the Euclidean plane. The question of what happens in these problems if one considers normed spaces other than the Euclidean plane has been raised in the 1980s by Ulam and Erdős and attracted a lot of attention over the years. We give an essentially tight answer to both questions for almost all norms on , in a certain Baire categoric sense.

For the unit distance problem we prove that for almost all norms ||.|| on , any set of points defines at most unit distances according to ||.||. We also show that this is essentially tight, by proving that for every norm ||.|| on , for any large , we can find $latex n$ points defining at least unit distances according to ||.||.

For the distinct distances problem, we prove that for almost all norms ||.|| on any set of points defines at least $latex (1−o(1))n$ distinct distances according to ||.||. This is clearly tight up to the $latex o(1)$ term.

Our results settle, in a strong and somewhat surprising form, problems and conjectures of Brass, of Matoušek, and of Brass-Moser-Pach. The proofs combine combinatorial and geometric ideas with tools from Linear Algebra, Topology and Algebraic Geometry.

We discussed the unit distances and distinct distances in many posts over here, and they are also related to problems around Borsuk’s problem (see also my survey paper Some old and new problems in combinatorial geometry I: Around Borsuk’s problem).

Standard boxes

Here is the abstract of Tomon’s paper.

We discussed the intersection pattern of (standard) boxes on several occasions such as this post about Jurgen Eckhoff.