# Combinatorics and Geometry Days III

Combinatorics and Geometry Days III is following our two previous events with the same name: Combinatorics and Geometry Days I that took place in Dolgoprudny, and online conference Combinatorics and Geometry Days II (videos and slides are provided on the event page).

## participate

## Speakers

## Schedule

**Section 1**chaired by Grigory Ivanov

A practical way to encode a manifold is to triangulate it. Among all possible triangulations it makes sense to look for the minimal one, which for the purpose of this talk means using the least number of vertices.

Consider now a family of manifolds such as $S^n$, ${\mathbb R}P^n$, $SO_n$, etc. A natural question is how the size of the minimal triangulation depends on $n$? Surprisingly, except for the trivial case of $S^n$, our best lower and upper bounds are very far apart.

For ${\mathbb R}P^n$ the best current are around $n^2$ and $\phi^n$, respectively, where $\phi$ is the golden ratio. In this talk I will present the first triangulation of ${\mathbb R}P^n$ with a subexponential, $e^{(\frac{1}{2}+o(1))\sqrt{n}{\log n}}$, number of vertices.

Tverberg-type theory aims to establish sufficient conditions for a simplicial complex $\Sigma$ such that every continuous map $f:\Sigma \to \mathbb{R}^d$ maps $q$ points from pairwise disjoint faces to the same point in $\mathbb{R}^d$. Such results are plentiful for $q$ a prime power. However, for $q$ with at least two distinct prime divisors, results that guarantee the existence of $q$-fold points of coincidence are non-existent— aside from immediate corollaries of the prime power case. Here we present a general method that yields such results beyond the case of prime powers.

In this talk I'll introduce Helly numbers for (discrete) point sets and explain why finite Helly numbers exist for periodic and certain quasiperiodic sets in Euclidean space of any dimension though the bounds in the latter case seem to be extremely non-optimal. I'll also show that for a wider class of Meyer sets Helly numbers could be infinite.

**Section 2**chaired by Grigory Ivanov

We consider quantitative versions of Helly-type questions. Our main result is a Quantitative Fractional Helly Theorem, which states that if $\mathcal{C}$ is a finite family of convex sets in $\mathbb{R}^d$, and a positive fraction of the $(3d+1)$-tuples have intersections with volume at least one, then $\mathcal{C}$ has a subfamily, whose members has intersection with volume at least $d^{O(-d^2)}$ and which contains a positive fraction of the sets from $\mathcal{C}$. From that, we deduce a Quantitative $(p,q)$-Theorem with $q = 3d+1$.

We extend the notion of the smallest volume ellipsoid containing a convex body in $R^d$ to the setting of logarithmically concave functions. We consider a vast class of logarithmically concave functions whose superlevel sets are concentric ellipsoids. For a fixed function from this class, we consider the set of all its "affine" positions. For any log-concave function f on R^d, we consider functions belonging to this set of "affine" positions, and find the one with the smallest integral under the condition that it is pointwise greater than or equal to f. We study the properties of existence and uniqueness of the solution to this problem. Finally, extending the notion of the outer volume ratio, we define the outer integral ratio of a log-concave function and give an asymptotically tight bound on it.

We study a long standing open problem by Ulam, which is whether the Euclidean ball is the unique body of uniform density which will float in equilibrium in any direction. We answer this problem in the class of origin symmetric n-dimensional convex bodies whose relative density to water is 1/2. For n=3, this result is due to Falconer.

**Section 1**chaired by János Pach

Elekes and Erdős proved that for any triangle, $T,$ there are $n$-element planar point sets with $\Omega(n^2)$ triangles similar to $T.$ It was proved shortly after that if the number of equilateral triangles is at least $(1/6+\epsilon)n^2$ then the pointset should contain large parts of a triangular lattice. On the other hand, no lattice is guaranteed for $cn^2$ similar copies if $c<1/6.$ We will show that one can still expect some structural results for triangles, even if the number of similar copies is as low as $n^{11/6+\epsilon}.$

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. A classical theorem due to Kővári, Sós and Turán says that this number of edges is $O\left(n^{2 - 1/k}\right)$. An important variant of this problem 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$. A remarkable result of Fox, Pach, Sheffer, Suk and Zahl with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on $n$ vertices and with no copy of $K_{k,k}$ as a subgraph must be $O\left(n^{2 - 1/d}\right)$. This theorem is sharp when $d=2$, because any $K_{2,2}$-free graph has VC-dimension at most $2$, and there are well-known examples of such graphs with $\Omega\left(n^{3/2}\right)$ edges. However, it turns out this phenomenon no longer carries through for any larger $d$.

We show the following improved result: the maximum number of edges in bipartite graphs with no copies of $K_{k,k}$ and VC-dimension at most $d$ is $o(n^{2-1/d})$, for every $k \geq d \geq 3$.

We call a multigraph *non-homotopic* if it can be drawn in the plane in such
a way that no two edges connecting the same pair of vertices can be continuously transformed into
each other without passing through a vertex, and no loop can be shrunk to its end-vertex in the
same way. It is easy to see that a non-homotopic multigraph on $n>1$ vertices can have arbitrarily
many edges. We prove that the number of crossings between the edges of a non-homotopic multigraph
with $n$ vertices and $m>4n$ edges is larger than $c\frac{m^2}{n}$ for some constant $c>0$, and
that this bound is tight up to a polylogarithmic factor. We also show that the lower bound is not
asymptotically sharp as $n$ is fixed and $m\longrightarrow\infty$

Given a set $P$ of $n$ points in general position in the plane, Jamison conjectured in 1986 that if $P$ determines at most $m \leq 2n-C$ distinct directions, then $P$ is contained in the set of vertices of a regular $m$-gon. Jamison verified his conjecture for $m=n$ and recently the case $m=n+1$ was proved by Pilatte. We will discuss this conjecture and prove it in the case $m \leq n +O(\sqrt{n})$.

**Section 1**chaired by Oleg Musin

In the first part of the talk, we present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E8 is the unique solution for the kissing number problem on the hemisphere in dimension 8.

However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, we explain how, via our rounding procedure, we can obtain an exact rational solution of semidefinite program from an approximate solution in floating point given by the solver.

The average kissing number of $R^n$ is the supremum of the average degrees of contact graphs of packings of finitely many balls (of any radii) in $R^n$. In this talk I will provide an upper bound for the average kissing number based on semidefinite programming that improves previous bounds in dimensions 3, ..., 9. A very simple upper bound for the average kissing number is twice the kissing number; in dimensions 6, ..., 9 our new bound is the first to improve on this simple upper bound.

Consider the Euclidean space R^n with an even dimension n. Equipped with a nondegenerate and alternating (sometimes called skew-symmetric) bilinear form this is referred to as a symplectic space. Symplectic spaces appear for instance if we express classical mechanics in a general way. The interest in the study of symplectic spaces arose in the 1980s due to the celebrated non-squeezing theorem by Gromov. In particular, Gromov's result required the existence of symplectic invariants, so called symplectic capacities. A symplectic capacity maps a nonnegative number to each subset of R^n while fulfilling certain properties. By now, several families of such invariants have been found. However, they are notoriously hard to compute. In my talk I will introduce a specific symplectic capacity, i.e. the Ekeland-Hofer-Zehnder (EHZ) capacity, restricted to polytopes. More precisely, I will state a result by Abbondandolo and Majer which formulates the EHZ capacity as an optimization problem. Afterwards, I will discuss this optimization problem in more detail as well as strategies to solve it.

We classify all sets of nonzero vectors in $R^3$ such that the angle formed by each pair is a rational multiple of $\pi$. The special case of four-element subsets lets us classify all tetrahedra whose dihedral angles are multiples of $\pi$, solving a 1976 problem of Conway and Jones: there are $2$ one-parameter families and $59$ sporadic tetrahedra, all but three of which are related to either the icosidodecahedron or the $B_3$ root lattice. The proof requires the solution in roots of unity of a $W(D_6)$-symmetric polynomial equation with $105$ monomials (the previous record was only $12$ monomials).

**Section 2**chaired by Alexander Kolpakov

The *Mastodon theorem* (PD., D. Legg, D. Townsend, 2002), establishes that the
regular bi-pyramid (North and South poles, and an equilateral triangle on the Equator) is the unique
up to rotation five-point configuration on the sphere that maximizes the product of all mutual (Euclidean)
distances.

In a joint work with Oleg Musin we generalize the Mastodon Theorem to $n+2$ points on $\mathbb{S}^{n-1}$, namely we characterize all stationary configurations, and show that all local minima occur when a configuration splits in two orthogonal simplexes of $k$ and $\ell$ vertices, $k+\ell=n+2$, with global minimum attained when $k=\ell$ or $k=\ell+1$ depending on the parity of $n$.

We consider the majorization (Karamata) inequality and minimums of the majorization (M-sets) for f-energy potentials of m-point configurations in a sphere. In particular, we discuss the optimality of regular simplexes, describe M-sets with a small number of points, define and discuss spherical f-designs.

A closed polygonal curve is called integral if it is composed of unit segments. Kenyon's problem asks whether for every integral curve, there is a dome over this curve, i.e. whether the curve is a boundary of a polyhedral surface whose faces are equilateral triangles with unit edge lengths. In this talk, we will give a necessary algebraic condition when the curve is a quadrilateral, thus giving a negative solution to Kenyon's problem in full generality. We will then explain why domes exist over a dense set of integral curves and give an explicit construction of domes over all regular polygons. Finally, we will formulate several open questions related to the initial problem of Kenyon.