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.

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.

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.

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.

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.

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.

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.

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.

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.

To be announced

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.

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

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.

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.

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.