Combinatorics and Geometry Days III at MIPT

Combinatorics and Geometry Days III

at MIPT
December 2 - 4, 2020
Online

The conference aims to be a meeting point for combinatorialists and geometers, where they will be able to present and discuss their current research, as well as give broader scope lectures accessible to interested PhD and master students.

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

All of the talks will be held on the zoom meeting:

Meeting ID: TBA
Password: first 6 decimal places of $\pi$

If you wish to recieve the updates and reminders via email, you are very welcome to register.
The registration is not required.

Speakers

Sergey Avvakumov University of Copenhagen, Denmark Maria Dostert KTH Royal Institute of Technology, Stockholm Peter Dragnev Purdue University Fort Wayne, US Alexey Garber University of Texas Rio Grande Valley, US Alexey Glazyrin University of Texas Rio Grande Valley, US Olivér Janzer ETH Zürich, Switzerland Attila Jung Institute of Mathematics, ELTE Eötvös Loránd University, Hungary Alexander Kolpakov University of Neuchâtel, Switzerland Stefan Krupp University of Cologne, Germany
Alexander Litvak University of Alberta, Canada Philippe Moustrou UiT – The Arctic University of Norway Oleg Musin University of Texas Rio Grande Valley, US Rom Pinchasi Technion, Israel Pablo Soberon Baruch College, City University of New York, US József Solymosi University of British Columbia, Canada Géza Tóth Rényi Institute of Mathematics, Hungary Igor Tsiutsiurupa MIPT, Russia Elisabeth Werner Case Western Reserve University, US
Alexandr Polyanskii MIPT Andrei Raigorodskii MIPT Idzhad Sabitov Moscow State University Andrey Sergunin MIPT Dmitriy Shabanov MIPT and Moscow State University Rom Pinchasi (tentatively) Technion, Israel and MIPT, Moscow

Abstracts

We will publish topics and abstracts of the talks in this section.
April 13
Section 1 chaired by Alexandr Polyanskii
15.10 - 15.30 MSK (UTC +3)
Sergey Avvakumov University of Copenhagen, Denmark
A subexponential size ${\mathbb R}P^n$
joint work with Karim Adiprasito and Roman Karasev
Room: 424 Arctica
Video Slides

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.

15.10 - 15.30 MSK (UTC +3)
Maria Dostert KTH Royal Institute of Technology, Stockholm
Semidefinite programming bounds for the average kissing number
joint work with Alexander Kolpakov and Fernando Mário de Oliveira Filho
Room: 424 Arctica
Video Slides

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.

15.10 - 15.30 MSK (UTC +3)
Alexey Garber University of Texas Rio Grande Valley, US
Helly numbers for crystals and cut-and-project sets
Room: 424 Arctica
Video Slides

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.

15.10 - 15.30 MSK (UTC +3)
Alexey Glazyrin University of Texas Rio Grande Valley, US
Domes over curves
joint work with Igor Pak from UCLA
Room: 424 Arctica
Video Slides

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.

15.40 - 16.10 MSK (UTC +3)
Olivér Janzer ETH Zürich, Switzerland
On the Zarankiewicz problem for graphs with bounded VC-dimension
joint work with Cosmin Pohoata
Room: 424 Arctica
Video Slides

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

15.40 - 16.10 MSK (UTC +3)
Attila Jung Institute of Mathematics, ELTE Eötvös Loránd University, Hungary
Quantitative Fractional Helly and (p,q)-Theorems
joint work with Márton Naszódi
Room: 424 Arctica
Video Slides

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

15.40 - 16.10 MSK (UTC +3)
Alexander Kolpakov University of Neuchâtel, Switzerland
Space vectors forming rational angles: on a question of J.H. Conway
joint work with Kiran Kedlaya, Bjorn Poonen, and Michael Rubinstein
Room: 424 Arctica
Video Slides

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

15.40 - 16.10 MSK (UTC +3)
Stefan Krupp University of Cologne, Germany
Calculating the EHZ Capacity of Polytopes
joint work with Daniel Rudolf (Ruhr-University Bochum)
Room: 424 Arctica
Video Slides

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.

15.40 - 16.10 MSK (UTC +3)
Alexander Litvak University of Alberta, Canada
A remark on the minimal dispersion
Room: 424 Arctica
Video Slides

We improve known upper bounds for the minimal dispersion of a point set in the unit cube and its inverse. Some of our bounds are sharp up to logarithmic factors.

15.40 - 16.10 MSK (UTC +3)
Philippe Moustrou UiT – The Arctic University of Norway
Exact semidefinite programming bounds for packing problems
joint work with Maria Dostert and David de Laat
Room: 424 Arctica
Video Slides

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.

15.40 - 16.10 MSK (UTC +3)
Rom Pinchasi Technion, Israel
Conics and Small Number of Distinct Directions
based on joint works with Mehdi Makhul and with Alexandr Polyanskii
Room: 424 Arctica
Video Slides

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})$.

15.40 - 16.10 MSK (UTC +3)
József Solymosi University of British Columbia, Canada
Planar point sets with many similar triangles
joint work with Dhruv Mubayi
Room: 424 Arctica
Video Slides

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}.$

15.40 - 16.10 MSK (UTC +3)
Géza Tóth Rényi Institute of Mathematics, Hungary
Crossings between non-homotopic edges
joint work with János Pach and Gábor Tardos
Room: 424 Arctica
Video Slides

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$

15.40 - 16.10 MSK (UTC +3)
Igor Tsiutsiurupa MIPT, Russia
Functional Lowner Ellipsoid
joint work with Grigory Ivanov
Room: 424 Arctica
Video Slides

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.

15.40 - 16.10 MSK (UTC +3)
Elisabeth Werner Case Western Reserve University, US
Convex Floating Bodies of Equilibrium
based on joint work with D.I. Florentin, C. Schuett and N. Zhang
Room: 424 Arctica
Video Slides

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.

April 15

Program Committee

Grigory Ivanov MIPT Andrey Kupavskii MIPT Oleg Musin University of Texas Rio Grande Valley
János Pach MIPT and Rényi Institute of Mathematics Alexandr Polyanskii MIPT

Local Organizing Committee

Sergei Kiselev Laboratory of Combinatorial and Geometric Structures, MIPT Andrey Kupavskii Laboratory of Combinatorial and Geometric Structures, MIPT Victor Mironov Laboratory of Combinatorial and Geometric Structures, MIPT
Andrey Raigorodskii Phystech School of Applied Mathematics and Informatics, Laboratory of Advanced Combinatorics and Network Applications, MIPT Yulia Rylova Laboratory of Combinatorial and Geometric Structures, MIPT