This talk is a survey including recent joint works with Kazufumi Eto, Shosaku Matsuzaki, ‪Mario Eudave-Muñoz, Kai Ishihara, Yuya Koda and Koya Shimokawa.

As a generalization of a graph, we define a multibranched surface as follows. Let $B$ be a closed 1-dimensional manifold, $S$ be a compact 2-dimensional manifold with non-empty boundary and $\phi: \partial S\to B$ be a covering map. Then the quotient space $X=B\cup_{\phi} S$ is called a multibranched surface.

Similarly to the genus of a graph, we define the genus of a regular multibranched surface $X$ as the minimum Heegaard genus of closed orientable 3-manifolds into which $X$ can be embedded. We give several upper bounds and lower bounds for the genus of a regular multibranched surface.

Similarly to the graph minor, we also introduce a minor on multibranched surfaces, and consider the obstruction set $\Omega(\mathcal{P}_{S^3})$ for the set of multibranched surfaces embedded in the 3-sphere. We summarize all known results on the obstruction set $\Omega(\mathcal{P}_{S^3})$ at the present moment.

1. K. Eto, S. Matsuzaki, M. Ozawa, An obstruction to embedding 2-dimensional complexes into the 3-sphere. Topol. Appl. 198 (2016), 117-125.
2. M. Eudave-Muñoz, M. Ozawa, Characterization of 3-punctured spheres in non-hyperbolic link exteriors. Topol. Appl. 264 (2019), 300-312.
3. M. Eudave-Muñoz, M. Ozawa, The maximum and minimum genus of a multibranched surface. Topol. Appl. (2020), 107502.
4. K. Ishihara, Y. Koda, M. Ozawa, K. Shimokawa, Neighborhood equivalence for multibranched surfaces in 3-manifolds. Topol. Appl. 257 (2019), 11-21.
5. S. Matsuzaki, M. Ozawa, Genera and minors of multibranched surfaces. Topol. Appl. 230 (2017), 621–638.
6. M. Ozawa, A partial order on multibranched surfaces in 3-manifolds. Topol. Appl. 272 (2020), 107074.

Algorithms for recognizing graph planarity are well-known. The classical topics in mathematics and computer science is recognizing realizability of hypergraphs in $d$-dimensional Euclidean space $\mathbb R^d$. In these studies, as well as in studies of Radon–Tverberg-type problems from topological combinatorics, the following notion appeared, see e.g. survey [5]. Denote by $\Delta_n$ a simplex with $n$ vertices. The body (or geometric realization) $|K|$ of a hypergraph $K=(V,E)$ is the union of faces of $\Delta_{|V|}$ corresponding to elements of $E$. An almost $r$-embedding of a hypergraph $K$ is a piecewise-linear (PL) map $f\colon |K|\to \mathbb R^d$ such that the images of any $r$ pairwise disjoint faces of $|K|$ do not have a common point. A $k$-dimensional hypergraph is a hypergraph whose maximal hyperedge has $k$ elements. By general position, for $(r-1)d>rk$ every $k$-dimensional hypergraph almost $r$-embeds in $\mathbb R^d$. For fixed $r$ and $d$, a polynomial algorithm for recognition almost $r$-embeddability of $k$-hypergraphs in $\mathbb R^d$ was constructed

• in [2, 1] for $(r-1)d=rk$;
• in [4] for $rd\ge(r+1)k+3$, see also [3].

1. S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, Eliminating Higher-Multiplicity Intersections, III. Codimension 2. Israel J. Math., to appear, arXiv:1511.03501.
2. I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, I. A Whitney Trick for Tverberg-Type Problems. arXiv:1508.02349.
3. I. Mabillard and U. Wagner, Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the $r$-Metastable Range. arXiv:1601.00876.
4. A. Skopenkov, Eliminating higher-multiplicity intersections in the metastable dimension range. arXiv:1704.00143.
5. A. Skopenkov, Invariants of graph drawings in the plane. abridged version: Arnold Math. J. 2020, full version: arXiv:1805.10237.

We discuss some classical problems of mathematical economics, in particular, the so-called envy-free division problems. The classical approach to some of such problem 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 on the map.

We try to replace the boundary condition by a certain equivariance condition under all permutations, or a weaker condition of "pseudoequivariance", 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 a certain type of the segment partition problem. The solution can be guaranteed if and only if the number of players is a prime power. The case of three players was solved previously be 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 a double prime power, the counterexamples showing that the topological configuration space / text map scheme for a wide class of equipartition problems fails (this result was completed in the follow-up paper [4] by Sergey Avvakumov and Sergey Kudrya). The existence of equivariant maps is applicable, for example, to building stronger counterexamples for the topological Tverberg conjecture (in another joint work [3] with Sergey Avvakumov and Arkadiy Skopenkov).

Though, under additional assumptions that every piece is estimated independently of the other pieces and the every player's estimate is the same we cannot drop the prime power assumption and have equipartitions, as in [1, 5].

1. Arseniy Akopyan, Sergey Avvakumov, and Roman Karasev, Convex fair partitions into an arbitrary number of pieces. arXiv:1804.03057.
2. Sergey Avvakumov and Roman Karasev, Envy-free division using mapping degree. arXiv:1907.11183.
3. Sergey Avvakumov, Roman Karasev, Arkadiy Skopenkov, Stronger counterexamples to the topological Tverberg conjecture. arXiv:1908.08731.
4. Sergey Avvakumov and Sergey Kudrya, Vanishing of all equivariant obstructions and the mapping degree. arXiv:1910.12628.
5. Sergey Avvakumov and Roman Karasev, Equipartition of a segment. arXiv:2009.09862.

A particular case of the main result is a direct proof of the implication $(LVKF_{1,3})\Rightarrow( LTT_{2,3})$:

• ($LVKF_{1,3}$) From any 11 points in $ \mathbb{R}^{3}$ one can choose 3 pairwise disjoint triples whose convex hulls have a common point.
• ($LTT_{2,3}$) Any 7 points in $\mathbb{R}^{2}$ can be decomposed into 3 subsets whose convex hulls have a common point.

These statements are true, but the purpose of this paper is the direct derivation of one statement from another.

1. E. Kolpakov, A 'converse' to the Constraint Lemma. arXiv:1903.08910.

Joint work with Rade T. Živaljević

The classical approach to envy-free division problems arising in mathematical economics typically relies on the Knaster–Kuratowski–Mazurkiewicz theorem, Sperner's lemma or some extension involving mapping degree. We propose a different approach which uses equivariant topology, originally developed for applications in discrete and computational geometry (Tverberg type problems, necklace splitting problem in the sense of N. Alon and D. West, etc.).

We prove several relatives of the classical envy-free division theorem, where the emphasis is on preferences allowing the players to choose degenerate pieces of the cake.

Assume that a group of $r$ players want to divide among themselves a "cake", that is, the interval $I=[0, 1]$, which should be cut into $r$ tiles. Therefore a cut of the cake in this model is a sequence of numbers $$0 \leqslant x_1 \leqslant x_2 \leqslant \dots \leqslant x_{r-1} \leqslant 1 \, .$$ After a cut is fixed, each of the players expresses his own individual preferences over the tiles, by pointing to one (or more) intervals which they like more than the rest.

A classical theorem, found independently by Stromquist and by Woodall in 1980 states that, under two conditions: (1) the closeness condition, and (2) "no player prefers a tile which degenerates to a single point", it is possible to divide the cake into $r$ connected tiles and distribute these shares to $r$ players in an envy-free manner: each player prefers a preferred share.

In our research we relax the condition (2) and instead make a very mild assumption $\mathbf{(P_{dte})}$: All degenerate tiles are equal. That is, for a fixed cut, each player either prefers all the degenerate tiles, or prefers none of the degenerate tiles.

What is known:

1. If $r$ is a prime power then an envy-free division always exists if the preferences satisfy some additional partition equivalence condition (Avvakumov and Karasev; see also Meunier and Zerbib in the cases when $r$ is a prime or $r=4$).
2. If $r$ is not a prime power, (a) is no longer true (Avvakumov and Karasev).
3. If it is allowed to drop some of the tiles, an envy-free division always exists under the condition $\mathbf{P_{dte}}$ (Avvakumov, Karasev, Meunier and Zerbib).

What is new:

1. We modify the rules of the game. In the presence of degenerate tiles only one of the guests may be given two tiles (instead of one) in which case one of them must be the rightmost tile. Then, if either $r$ is a prime number or $r=4$, under the condition $\mathbf{P_{dte}}$, an envy-free division always exists.
2. If $r$ is neither a prime nor equal to $4$, the statement A is not true.
3. Let $r$ be a prime number or $r=4$. Suppose that we are allowed to drop at most one of the non-degenerate tiles. With an additional small assumption concerning the tile number $r$, an envy-free division always exist under the condition $\mathbf{P_{dte}}$.
4. Statement A yields an alternative proof of the result a of Avvakumov and Karasev.
5. Assume that the tiles may be distributed among the players without any restrictions, in particular a player may receive several tiles at a time. Then under the condition $\mathbf{P_{dte}}$, an envy-free division always exists if $r$ is a prime power.

Joint work with Duško Jojić and Gaiane Panina

The colored Tverberg theorem of Blagojević, Matschke, and Ziegler provides optimal bounds for the colored Tverberg problem, under the condition that the number of intersecting rainbow simplices is a prime number.

One of our principal new ideas is to replace the ambient simplex $\Delta^N$, used in the original Tverberg theorem, by an "abridged simplex" of smaller dimension, and to compensate for this reduction by allowing vertices to repeatedly appear a controlled number of times in different rainbow simplices.

Following this strategy we obtain an extension of the result of Blagojević, Matschke, and Ziegler to an optimal colored Tverberg theorem for multisets of colored points, which is valid for each prime power $r=p^k$, and reduces to their result for $k=1$.

Configuration spaces, used in the proof, are combinatorial pseudomanifolds which can be represented as multiple chessboard complexes. Our main topological tool is the Eilenberg–Krasnoselskii theory of degrees of equivariant maps for non-free actions.

Joint work with L. Vokřínek

The study of algorithmic solutions to classical problems in homotopy theory such as the computation of set $[X,Y]$ of homotopy classes of maps or the lifting-extension problem can be traced back to the 50's. In recent years, the area saw a rapid development and new results were applied to problems of computational topology, such as the embeddability problem i.e. the question whether a $k$-dimensional simplicial complex $K$ is embeddable in $\mathbb{R}^d$, see [1, 2].

We present a polynomial-time algorithm that, given topological spaces $X,Y$ (modeled by finite simplicial complexes) with an action of a finite group $G$, computes the set $[X,Y]_G$ of homotopy classes of equivariant maps under the so-called stable condition $\dim X^H \leq 2~\mathrm{conn}(Y^H) > 1$, for all subgroups $H\leq G$. In fact the result follows from a more general study of homotopy classes of maps between diagrams of spaces.

Consider now the $r$-Tverberg problem: Given a $k$-dimensional simplicial complex $K$, decide whether there is a (piecewise-linear) map (called $r$-Tverberg map) $K \to \mathbb{R}^{d}$ without $r$-tuple intersection points on $r$ pairwise disjoint faces. Notice that if $r = 2$, we obtain the embeddability problem.

For $r>2$, Mabillard and Wagner [3, 4] established a version of the Haefliger–Weber theorem: In the metastable range $rd \geq (r+1)k +3$, the $r$-Tverberg problem is equivalent to deciding an existence of an equivariant map between spaces with non-free actions of the symmetric group $\mathsf{S}_r$. Thus to solve the problem it is enough to determine whether certain set of the form $[X,Y]_{\mathsf{S}_r}$ is nonempty. Applying our result here, we conclude that in the metastable range of dimensions, the $r$-Tverberg problem is decidable in polynomial time.

1. Martin Čadek, ‪Marek Krčál, Lukáš Vokřínek, Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom., 57(4):915--965, 2017.
2. Marek Filakovský, Uli Wagner, and Stephan Zhechev, Embeddability of simplicial complexes is undecidable. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767--785. Society for Industrial and Applied Mathematics, January 2020.
3. I. Mabillard and U. Wagner, Eliminating Tverberg points, I. An analogue of the Whitney trick. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 171:171--171:180, New York, NY, USA, 2014. ACM.
4. Isaac Mabillard and Uli Wagner, Eliminating higher-multiplicity intersections, II. The deleted product criterion in the $r$-metastable range. In Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), pages 51:1--51:12, 2016.

Joint work with M. Tancer

Proving many combinatorial and geometrical results such as Radon's or Helly's theorem requires a stronger notion of non-embeddability. Namely, we require that for any continuous map $f\colon K\to X$ of the given simplicial complex $K$ into the target topological space $X$ there are two disjoint simplices in $K$, whose images in $X$ intersect. Fortunately the classical approach via equivariant topology establishes even stronger $\mathbb Z_2$-version of non-embeddability.

In this talk we focus on non-embedabbility of $k$-complexes $K$ into $2k$-manifolds $M$. There are many cases where all the notions of non-embeddability coincide, e.g. if $M$ is a projective plane or torus, or if $K$ is a complete $k$-skeleton of a simplex and $M=\mathbb R^{2k}$.

However, if $M$ is a surface of sufficiently high genus, the situation is different. Fulek and Kynčl have found a graph that can be $\mathbb Z_2$-almost embedded into a surface of genus $4$, but cannot be embedded there. Hence, if we want to establish tight non-almost-embeddability results for surfaces, we need to study more general $\mathbb Z$-almost embeddability.

We describe a general obstruction for non-embeddability of $k$-complexes into $2k$-manifolds over $\mathbb Z$. The obstruction leads to an explicit system of quadratic diophantine equations. In many cases it can be shown that these equations cannot be satisfied, and hence there is no $\mathbb Z$-embedding. We note that there have been some prior work on embeddings of $k$-complexes into manifolds, however we are the first ones who describe such an obstruction explicitly. As an example, let us mention that in 1969 Harris published an obstruction for embeddings of simplicial complexes into manifolds. However, constructing Harris's obstruction requires several steps that are provably undecidable. Our work produces a system of quadratic diophantine equations of a very special form. The decidability of such systems is yet to be determined.

We say a $d$-dimensional simplicial complex embeds into double dimension if it embeds into the Euclidean space of dimension $2d$. For instance, a graph is planar if and only if it embeds into the double dimension. If two simplicial complexes K and L are not embeddable into double dimension, what can we say about their join complex K*L? In this talk, I consider this problem and sketch a proof of the fact that, quite unexpectedly, there are complexes K and L which are not embeddable into double dimension but their join is embeddable into double dimension. More generally, I discuss conditions under which the join is non-embeddable into double dimension.

The classical obstruction for embedding a simplicial complex $K$ into double dimension is called the van Kampen obstruction. This is a cohomology class in the quotient of the deleted product of $K$. This class can also be defined as an Smith classes. Simth classes are our main tool and I discuss these classes. Moreover, it is possible to use the deleted join instead of the deleted product to define the obstruction to embeddability. It follows that the problem of embeddability of the join complex $K*L$ relates to the behavior of the Smith index of a $\mathbb{Z}_2$-complex under join. We determine this behavior to some extent for Smith classes of $\mathbb{Z}_p$-complexes, for $p$ prime.

In order to show that a cohomology class is non-zero, we use chains, which we call certificates, with special properties. This method allows us to prove that some "product" of cohomology classes is non-zero by constructing certificates for the product class based on certificates for the factors. Details can be found in [1].

1. S. Parsa, Instability of the Smith Index Under Joins and Applications to Embeddability. Arxiv preprint: arXiv:2103.02563, 2021.

Joint work with Catherine Greenhill, Mikhail Isaev and Tamás Makai

Let $\mathbf{d}=(d_1,\ldots,d_n)$ be a sequence of integers, and let $P_r(\mathbf{d})$ be the probability that a uniformly random $r$-uniform hypergraph has degree sequence $\mathbf{d}$. Our aim is to estimate this probability. The best results so far were obtained by Kamčev, Liebenau and Wormald (arXiv, 2020), who covered degree sequences from very sparse to moderately dense. In the moderately dense range, which overlaps with ours, they require $r=o(n^{1/4})$, a density $O(1/r)$ of the complete hypergraph, and a maximum variation of the degrees that is small but large enough to cover the typical degrees of random hypergraphs. In our work we extend their result into the arbitrarily dense domain. We also remove the restriction on $r$ completely, and allow a much greater variation of degrees. One of the corollaries is a proof (for our range of densities) of a conjecture of Kamčev et al that the degrees of random hypergraphs almost everywhere match a vector of independent hypergeometric variables conditioned on given sum.

The design of learning-augmented online algorithms is a new and active research area. The goal is to understand how to best incorporate predictions of the future provided e.g. by machine learning algorithms that rarely come with guarantees on their accuracy.

In the absence of guarantees, the difficulty in the design of such learning-augmented algorithms is to find a good balance: on the one hand, following blindly the prediction might lead to a very bad solution if the prediction is misleading. On the other hand, if the algorithm does not trust the prediction at all, it will simply never benefit from an excellent prediction. An explosion of recent results solve this issue by designing smart algorithms that exploit the problem structure to achieve a good trade-off between these two cases.

In this talk, we will discuss this emerging line of work. In particular, we will show how to unify and generalize some of these results by extending the powerful primal-dual method for online algorithms to the learning augmented setting.

It is joint work with Lina Li, Ramon Garcia, Adam Wagner; and with Robert Krueger and Haoran Luo.

A family of subsets of $[n]$ is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics, starting with the well-known Erdös–Ko–Rado Theorem. We consider two extensions of it:

Counting variant: Frankl–Kupavskii and Balogh–Das–Liu–Sharifzadeh–Tran showed that for $n\geq 2k + c\sqrt{k\ln k}$, almost all $k$-uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for $n\geq 2k+ 100\ln k$.

Random variant: For positive integers $n$ and $k$ with $n\geq 2k+1$, the Kneser graph $K(n,k)$ is the graph with vertex set consisting of all $k$-sets of $\{1,\dots,n\}$, where two $k$-sets are adjacent exactly when they are disjoint. Let $K_p(n,k)$ be a random spanning subgraph of $K(n,k)$ where each edge is included independently with probability $p$. Bollob\'as, Narayanan, and Raigorodskii asked for what $p$ does $K_p(n,k)$ have the same independence number as $K(n,k)$ with high probability. Building on work of Das and Tran and of Devlin and Kahn, we resolve this question.

Our proofs uses, among others, the graph container method and the Das–Tran removal lemma.