CanaDAM 2021
On-line, May 25 - 28, 2021

Discrete Geometry
Org: Yufei Zhao (MIT)

DOR MINZER, Massachusetts Institute of Technology
Optimal tiling of the Euclidean space using permutation-symmetric bodies  [PDF]

What is the least surface area of a body $B$ whose $\mathbb{Z}^n$ translations tile $\mathbb{R}^n$? The isoperimetric inequality gives the bound $\Omega(\sqrt{n})$, and remarkably Kindler et al.\ showed that this is achievable.

In this work, we consider permutation-symmetric tilings. We show that in this case the answer is $\Theta(n/\sqrt{\log n})$.

Our work is motivated by the study of strong versions of the parallel repetition theorem, which if true would have significant applications. Unfortunately, strong parallel repetition fails in general [Raz]. Our result suggests there may be important special cases where it still applies.

Joint work with Mark Braverman.

COSMIN POHOATA, Yale University
On the Zarankiewicz problem for graphs with bounded VC-dimension  [PDF]

The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on $n$ vertices which does not contain the complete bipartite graph $K_{k,k}$ as a subgraph. In this talk, we will present some new phenomena related to an important variant of this problem, which is the analogous question in bipartite graphs with VC-dimension at most $d$, where $d$ is a fixed integer such that $k \geq d \geq 2$. Several connections with incidence geometry will also be discussed. Joint work with Oliver Janzer.

ALEXANDR POLYANSKII, Moscow Institute of Physics and Technology
A cap covering theorem  [PDF]

A cap of spherical radius $\alpha$ on a unit $d$-sphere $S$ is the set of points within spherical distance $\alpha$ from a given point on the sphere. Let $\mathcal F$ be a finite set of caps lying on $S$. We prove that if no hyperplane through the center of \( S \) divides $\mathcal F$ into two non-empty subsets without intersecting any cap in $\mathcal F$, then there is a cap of radius equal to the sum of radii of all caps in $\mathcal F$ covering all caps of $\mathcal F$ provided that the sum of radii is less $\pi/2$.

YAIR SHENFELD, Massachusetts Institute of Technology
Extremal structures of log-concave sequences via convex geometry  [PDF]

Many sequences arising naturally in combinatorics are known, or conjectured to be, concave after taking their logarithm. Suppose that such a sequence has a flat part, meaning that one term is equal to the average of its neighbors. What does this imply for the structure of the combinatorial objects at hand? Our recent resolution of the conjectures about the extremal structures of the Alexandrov-Fenchel inequalities in convex geometry allows us to tackle such questions. No background in convex geometry is assumed. Joint work with Ramon van Handel.

JOSH ZAHL, University of British Columbia
Sphere tangencies, line incidences, and Lie's line-sphere correspondence  [PDF]

In this talk I will discuss a connection between two problems in combinatorial geometry: bounding the maximum possible number of tangencies determined by a set of spheres in three dimensions, and bounding the maximum possible number of intersections determined by a set of lines in three dimensions. The connection between these two problems is given by Lie's line-sphere correspondence.