Конференция $А.М. ≥ 50$ в честь юбилея А.М. Райгородского в МФТИ

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.

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.