# Combinatorics and Geometry Days I

at MIPT
November 26 - 27, 2019
Dolgoprudny
MIPT
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.

## Speakers

Danila Cherkashin Chebyshev laboratory, St. Petersburg State University Alexandr Guterman Moscow State University and MIPT Nikita Kalinin Chebyshev laboratory, St. Petersburg State University and Higher School of Economics Roman Karasev MIPT Sergei Kiselev MIPT János Pach Renyi Institute, Université Paris-Est, and MIPT Fedor Petrov Steklov institute of RAS
Alexandr Polyanskii MIPT Andrei Raigorodskii MIPT Idzhad Sabitov Moscow State University Andrey Sergunin MIPT Dmitriy Shabanov MIPT and Moscow State University Gábor Tardos Renyi Institute and MIPT István Tomon ETH Zurich and MIPT

## Schedule

Here is the schedule of conference talks for November 26 and 27. There also will be an additional lecture by Gábor Tardos (November 28) and two lectures by István Tomon (November 29 and December 2), follow the links for more details.
November 26
9.40 - 10.30
Roman Karasev
Envy-free divisions and mapping degrees
joint work with Sergey Avvakumov, Arkadiy Skopenkov, and Sergey Kudrya
Room: 424 Arctica

We discuss some classical problems of mathematical economics, in particular, so-called envy-free division problems. The classical approach to some of such problems reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster–Kuratowski–Mazurkiewicz theorem and the Gale theorem) is a boundary condition.

We try to replace the boundary condition by a certain equivariance condition under all permutations, or a weaker condition of "pseudo-equivariance'', which has a certain real-life meaning for the problem of partitioning a segment and distributing the parts among the players. It turns out that we can guarantee the existence of a solution for the segment partition problem when the number of players is a prime power; and we may produce instances of the problem without a solution otherwise. The case of three players was solved previously by Segal–Halevi, the prime case and the case of four players were solved by Meunier and Zerbib.

Going back to the true equivariance setting, we provide, in the case when the number of players is not a prime power and not twice a prime power, the counterexamples showing that the topological configuration space / test map scheme for a wide class of equipartition problems fails and some envy-free division problems have a counterexample. Moreover, this is also applicable to building stronger counterexamples for the topological Tverberg conjecture.

10.40 - 11.10
Fedor Petrov
Degree sequence and the number of spanning trees
Room: 424 Arctica

For a finite connected graph define its Ehrenborg number as the number of spanning trees divided by the product of degrees of all vertices. We prove that it is $\mathbb{O}(\frac{1}{V})$, where $V$ is the number of vertices. It is a step to still open Richard Ehrenborg's conjecture which says that for a bipartite graph with part sizes $m$ and $n$ the Ehrenborg number does not exceed $\frac{1}{nm}$. There is a wide class of graphs, including complete bipartite, for which equality in this conjecture holds.

11.20 - 12.00
Dmitriy Shabanov
Probability thresholds for coloring properties of random hypergraphs
Room: 424 Arctica

The talk deals with the problems concerning colorings of random graphs and hypergraphs. Let $H(n,k,p)$ denote the classical binomial model of a random $k$-uniform hypergraph: every edge of a complete $k$-uniform hypergraph on $n$ vertices is included into $H(n,k,p)$ independently with probability $p\in(0,1)$. In the talk we will survey the recent advances concerning estimating the probability thresholds for coloring properties of random graphs and hypergraphs in the $H(n,k,p)$ model. We will consider:

• proper colorings (none of the edges is monochromatic);
• panchromatic colorings (every edge should contain the vertices of all the colors);
• strong colorings (every two vertices of the same color cannot share a common edge).

We will also discuss the proof technique based on the developed simple approach to the application of the second moment method.

12.00 - 14.20
Lunch
14.20 - 14.50
Nikita Kalinin
The number π and summation by SL(2, $Z$)
joint work with Mikhail Shkolnikov
Room: Lecture Hall 4th floor Arctica

The sum (resp. the sum of the squares) of the defects in the triangle inequalities for the area one lattice parallelograms in the first quadrant has a surprisingly simple expression. Namely, let $$f(a, b, c, d) = \sqrt{a^2 + b^2} + \sqrt{c^2 + d^2} - \sqrt{(a+c)^2 + (b+d)^2}.$$ Then, $$\sum f(a, b, c, d) = 2,$$ $$\sum f(a, b, c, d)^2 = 2 - \frac{\pi}{2},$$ where the sum runs by all $a, b, c, d \in Z \geq 0$ such that $ad − bc = 1$. This paper is devoted to the proof of these formulae. We also discuss possible directions in study of this phenomena.

Cancelled
Danila Cherkashin
Extremal problems in hypergraph colorings
Room: Lecture Hall 4th floor Arctica

The talk is devoted to problems on finding not-$r$-colorable hypergraphs with the minimal number of edges in a given hypergraph class. The central problem of this type is the Erdos--Hajnal that is to find the minimal number of edges in $n$-uniform hypergraph with chromatic number at least 3.

15.00 - 15.30
Alexandr Guterman
On Permanent Krauter Conjecture
The talk is based on the joint work with M.V. Budrevich.
Room: Lecture Hall 4th floor Arctica

The class of $(-1,1)$-matrices is very important in algebra, combinatorics and in various their applications. For example, well-known Hadamard matrices are of this type.

Two important functions in matrix theory, determinant and permanent, look very similar: $$\det A= \sum_{\sigma\in { S}_n} (-1)^{\sigma} a_{1\sigma(1)}\cdots a_{n\sigma(n)} \quad \mbox{ and } \quad per A= \sum_{\sigma\in { S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)}$$ here $A=(a_{ij})\in M_n(F)$ is an $n\times n$ matrix and ${ S}_n$ denotes the set of all permutations of the set $\{1,\ldots, n\}$.

While the computation of the determinant can be done in a polynomial time, it is still an open question, if there are such algorithms to compute the permanent. Therefore, any bounds on this function are actual.

In 1974 Wang posed a problem to find a decent upper bound for $|per(A)|$ if $A$ is a square $\pm 1$-matrix of rank $k$. In 1985 Krauter conjectured some concrete upper bound.

We prove the Krauter's conjecture and thus obtain the complete answer to the Wang's question. In particular, we characterized matrices with the maximal possible permanent for each value $k$ of the rank.

15.30 - 16.00
Coffee Break
Room: Lecture Hall 4th floor Arctica
16.00 - 17.00
Gábor Tardos
Extremal theory of vertex- and edge-ordered graphs (1st lecture out of 3)
Room: Lecture Hall 4th floor Arctica

The basic question of Turan type extremal graph theory is the maximum number of edges in a simple graph on n vertices that does not contain a specified "forbidden" subgraph (or any one of several forbidden subgraphs). This is a classical topic of combinatorics with many deep results and lot of questions that are still open.

In my survey talk I will focus on extensions of this theory to simple graphs with an additional structure, namely a linear order on the set of vertices or edges. A single simple graph has several vertex order and by forbidding just one of them we obtain different extremal questions. Introducing either a vertex- or an edge-order makes the theory richer and more suitable to (mostly geometric) applications.

I will highlight several specific open problems about both vertex- and edge-ordered graphs. I will mention results from numerous researchers, among them Balazs Keszegh, Daniel Korandi, Jesse Geneson, Daniel Gerbner, Adam Marcus, Abhishek Methuku, Daniel Nagy, Janos Pach, Seth Pettie, Domotor Palvolgyi, Istvan Tomon, Mate Vizer, Creig Weidert, etc.

November 27
9.40 - 10.30
János Pach
Strings and Order
Room: 119 Main Building

Let $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called $x$-monotone if every vertical line intersects it in at most one point.

We solve a 25 years old problem by showing that for arbitrarily large integers $k$, there exist families of $x$-monotone curves such that their disjointness graphs $G$ satisfy $\omega(G)=k$ and $\chi(G)=\Omega(k^4)$. This bound is asymptotically tight.

If we drop the condition that the curves are $x$-monotone, then $\chi(G)$ cannot be bounded in terms of $k$. We construct, for every $g>3$, families of $n$ curves such that the girth of their disjointness graphs $G$ is at least $g$ and $\chi(G)=\Omega_g(\log n)$. This improves a result of Bollobás. Joint work with István Tomon.

10.40 - 11.20
István Tomon
Turán number of bipartite graphs with no $K_{t,t}$
Room: 119 Main Building

The extremal number of a graph $H$, denoted by $\mbox{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The well known Kővári-Sós-Turán theorem says that for a complete bipartite graph with parts of size $t\leq s$ the extremal number is $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$. A celebrated generalization of this result, proved by Füredi and Alon-Krivelevich-Sudakov is that if $H$ is a bipartite graph such that every vertex in one part has degree at most $t$, then $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$ as well. In this talk, I will show that this bound can be improved if we also assume that $H$ does not contain $K_{t,t}$, which settles a conjecture of Conlon, Lee and Janzer.

11.30 - 14.00
Lunch
14.00 - 14.30
Andrei Raigorodskii
Random subgraphs of Johnson's graphs
Room: Lecture Hall 4th floor Arctica

Johnson's graph is a graph whose vertices are $r$-subsets of the set $[ \,n] \, = \{1, ..., n\}$ and edges — pairs of vertices with size of intersection $s$. We consider random subgraphs of Johnson's graphs and study the asymptotic behaviour of their independence numbers and chromatic numbers.

14.40 - 15.00
Andrey Sergunin
On the number of intersection points of lines and circles in $\mathbb{R}^3$
Room: Lecture Hall 4th floor Arctica

It is easy to see that $n$ lines in $\mathbb{R}^3$ can have a quadratic number of intersection points. For instance, consider $n$ lines in general position in the plane. Another example is $n$ lines on the surface of a hyperboloid with one sheet: $n/2$ of these lines belong to one family of generators, $n/2$ of these lines belong to another. But if there are no $\sqrt{n}$ lines lying on a surface of degree at most two, then the number of intersection points can be bounded by $O(n^{3/2})$.

We consider an analogous question about intersection points formed by curves of two families in $\mathbb{R}^3$: A family of $n$ lines and a family of $n$ circles.

It is easy to find examples of families of lines and circles with quadratic number of pairwise intersections: If all curves lie on a plane or on a surface of hyperboloid with one sheet. Suppose that there are no $\sqrt{n}$ curves lying on an algebraic surface of degree at most two. Under this condition, we proved that the number of points lying on at least one line and at least one circle is $O(n^{3/2})$.

15.10 - 15.30
Sergei Kiselev
Rainbow matchings in $k$-partite hypergraphs
Joint work with Andrey Kupavskii.
Room: Lecture Hall 4th floor Arctica

Let $[n]:=\{1,\ldots,n\}$. The following conjecture was made by Aharoni and Howard:

Conjecture: Let $n\ge s$ and $k$ be positive integers. If $\mathcal F_1,\ldots,\mathcal F_s\subset [n]^k$ satisfy $\min_{i}|\mathcal F_i|>(s-1)n^{k-1}$ then there exist $F_1\in\mathcal F_1,\ldots, F_s\in \mathcal F_s,$ such that $F_i\cap F_j = \emptyset$ for any $1\le i In their paper, Aharoni and Howard proved this conjecture for$k=2,3$. Then, Lu and Yu proved it for$n>3(s-1)(k-1).$The main result of this paper is the proof of the conjecture for all$s>s_0.$The proof relies on the idea that intersection of any family with a random matching is highly concentrated around its expectation. This idea was introduced by the second author in the paper in the context of the Erdős Matching Conjecture. Joint work with Andrey Kupavskii. 15.30 - 16.00 Coffee Break Room: Lecture Hall 4th floor Arctica 16.00 - 17.00 Gábor Tardos Extremal theory of vertex- and edge-ordered graphs (2nd lecture out of 3) Room: Lecture Hall 4th floor Arctica The basic question of Turan type extremal graph theory is the maximum number of edges in a simple graph on n vertices that does not contain a specified "forbidden" subgraph (or any one of several forbidden subgraphs). This is a classical topic of combinatorics with many deep results and lot of questions that are still open. In my survey talk I will focus on extensions of this theory to simple graphs with an additional structure, namely a linear order on the set of vertices or edges. A single simple graph has several vertex order and by forbidding just one of them we obtain different extremal questions. Introducing either a vertex- or an edge-order makes the theory richer and more suitable to (mostly geometric) applications. I will highlight several specific open problems about both vertex- and edge-ordered graphs. I will mention results from numerous researchers, among them Balazs Keszegh, Daniel Korandi, Jesse Geneson, Daniel Gerbner, Adam Marcus, Abhishek Methuku, Daniel Nagy, Janos Pach, Seth Pettie, Domotor Palvolgyi, Istvan Tomon, Mate Vizer, Creig Weidert, etc. 17.20 - 18.00 Idzhad Sabitov Volume polynomials for some classes of polyhedra Room: Lecture Hall 4th floor Arctica It is known that for any simplicial polyhedron$P$in the Euclidean 3-space there exists a polynomial such that the volume$V$of$P$is a root of the polynomial with coefficients depending only on the lengths of edges of$P$and its combinatorial structure, see e.g. our survey [1]. As a result we have that the volumes of all isometric polyhedra with the same combinatorial structure can be calculated as roots of a fixed polynomial. This fact gives a positive solution to "Bellows conjecture" affirming the invariance of the volume of a flexible polyhedron during its flexion. The existence of such a polynomial for volume of polyhedra is proved by the presentation of an explicit method of its construction. But in practice this method gives a polynomial with a very big number of monomials so the problem is to find a more effective method for their construction, namely for the construction of so-called canonical form of such polynomials having the least possible degree. This problem is solved now for polyhedra with$n=4,5$and$n=6$vertices, in particular for octahedra. In our talk we intend to show how one can use this knowledge in order to construct canonical volume polynomials for polyhedra combinatorially isomorphic to an$n$-prism in the cases$n = 4,5,6,7$that is for some polyhedra with$8,10,12,14$vertices. A detailed description of all necessary procedures is given in [2] and [3]. [1] I.Kh. Sabitov. Algebraic methods in the solution theory of polyhedra. Uspekhi math. nauk, 2011, v. 66, № 3, p. 3-67 (English translation: Russian Math, Surveys, 2011, 66:3, p. 445-505). [2] D.I. Sabitov, I.Kh. Sabitov. Volume polynomial for polyhedra of hexaedral type. Siberian Electronic Math, Reports, 2017, v.14, p. 1078-1087. [3] D.I. Sabitov, I.Kh. Sabitov. Volume polynomials for polyhedra combinatorially isometric to$n$-prisms in the cases$n=5,6,7\$. Siberian Electronic Math, Reports, 2019, v.16, p. 439-448.

## Location

The conference will take place at MIPT, Dolgoprudny.

If you are not a speaker of the conference or a MIPT student or employee and plan to attend the conference or the lectures of Gábor Tardos or István Tomon, please email Irina (kupavskaya.io@mipt.ru) and do not forget to take your (Russian) passport.

The conference location in MIPT camp: Arctica Building (Nauchny pereulok, 4) and the main Building (Institutskiy pereulok, 9), see the map below.

Trains from Moscow
To get to the MIPT campus from Moscow you can catch a suburban train at Savyolovskaya, Timiryazevskaya or Okruzhnaya platforms. Platforms are close to the metro stations with the same names. The ride on the train takes from 15 to 30 minutes to destination stations Novodachnaya or Dolgoprudnaya.
Buses from Moscow
There are buses to Dolgoprudny from Altufyevo (route 545) and Khovrino (route 368) metro stations. The ride on the bus takes from 30 to 50 minutes.
Taxi from Moscow
You can also take a taxi. Easiest way to do so is to use Yandex Taxi service on web or by phone +7 (495) 999 99 99.