Schedule for: 23w5023 - New trends from Classical Theorems in Geometry, Combinatorics, and Topology

Let $X$ be a finite set of points in d-dimensional space in general position. What is the maximum number of vertices that $conv(T (X))$ can have among all the possible permissible projective transformations $T$ ? In this talk, we discuss this and related questions in connection with Radon partitions, topes in arrangements of hyperplanes and balanced 2-coloring of points in the plane. This is a joint work with N. Garcia-Colin and L.P. Montejano.

We prove the following sparse approximation result for polytopes. Assume that $Q \subset \R^d$ is a polytope in John's position. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q'$ satisfies $Q \subseteq - 2d^2 \, Q'$. As a consequence, we retrieve the best bound for the quantitative Helly-type result for the volume, achieved by Brazitikos, and improve on the strongest bound for the quantitative Helly-type theorem for the diameter, shown by Ivanov and Nasz\'odi: We prove that given a finite family $\mathcal{F}$ of convex bodies in $\R^d$ with intersection $K$, we may select at most $2 d$ members of $\mathcal{F}$ such that their intersection has volume at most $(c d)^{3d /2} \vol K$, and it has diameter at most $2 d^2 \diam K$, for some absolute constant $c>0$.

Any point set P=\{x_1,\ldots,x_n\} in d-dimensional space induces a total preorder on the pairs (i,j) given by (i,j)<(k,l) if d(p_i,p_j) (Hotel Hacienda Los Laureles)

A decade ago two groups of authors, Karasev, Hubard, Aronov , Blagojević and Ziegler, have shown that the regular convex partitions of a Euclidean space into n parts yield a solution to the generalised Nandakumar and Ramana-Rao conjecture when n is a prime power. This was obtained by parametrising the space of regular equipartitions of a given convex body with the classical configuration space. Now, we repeat the process of regular convex partitions many times, first partitioning the Euclidean space into n_1 parts, then each part into n_2 parts, and so on. In this way we obtain iterated equipartions of a given convex body into n=n_1...n_k parts. We parametrise such iterated partitions by the (wreath) product of classical configuration spaces, and develop a new scheme for solving the generalised Nandakumar and Ramana Rao conjecture. The new scheme yields a solution to the conjecture if and only if all the n_i's are powers of the same prime. In particular, for the failure of the scheme outside prime power case we give three different proofs. (This lecture is based on the joint work with Pavle V. M. Blagojević.)

Radon theorem plays a basic role in many results of combinatorial convexity. It says that any set of d+2 points in R^d can be split into two parts so that their convex hulls intersect. It implies Helly theorem and as shown recently by Holmsen & Lee also its more robust version, so-called fractional Helly theorem. By standard techniques this consequently yields an existence of weak epsilon nets and a (p,q)-theorem. We will show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. More precisely, given an intersection-closed family F of subsets of R^d, we will measure the complexity of F by the supremum of the first d/2 Betti numbers over all elements of F. We show that constant complexity of F guarantees versions of all the results mentioned above, most notably that fractional Helly number of such families is d+1. Based on joint work with Xavier Goaoc and Andreas Holmsen.

We will present a general framework for treating problems of partitions of mass assignments with prescribed hyperplane arrangements on Euclidean vector bundles. Developing a new configuration test map scheme, as well as an alternative topological toolkit will allow us to reprove known results, extend them to arbitrary bundles as well as to put various types of constraints on the solutions. Moreover, the developed topological methods allow us to give new proofs and to extend results of Guth & Katz, Schnider, Soberón & Takahashi, and Blagojević, Calles Loperena, Crabb & Dimitrijević-Blagojević. In this way all these results will be under one ``roof''. (This lecture is based on the joint work with Michael C. Crabb.)

An early success story of topological methods in discrete geometry is the Ham Sandwich theorem, which states that any d finite point sets in $R^d$ can simultaneously be cut in half by an affine hyperplane. I will discuss generalizations to multiple hyperplanes, unbalanced cuts, and hyperplane transversals. Dolnikov's theorem states that any d pairwise intersecting families of polytopes in $R^d$ can be simultaneously pierced by one hyperplane. This generalizes the Ham Sandwich theorem. I will present variants of Dolnikov's theorem for multiple hyperplanes.

The multiparameter model $X(n; p_1, p_2, ...)$ generates a random simplicial complex on n vertices proceeding dimension by dimension by including each i-face with probability p_i conditioned on its boundary already being included. In this talk we'll discuss thresholds for the minimum dimension Euclidean space into which such a random complex embeds.

I will consider a generalization of Sperner’s lemma for triangulations of a d–dimensional polytope P whose vertices are colored in at most $m (Hotel Hacienda Los Laureles)

Consider $4$ grasshoppers sitting at the vertices of a square. In a ``legal move'', any one of them can jump over another, and land on its other side at exactly the same distance. After a finite number of legal moves, can the grasshoppers end up at the vertices of a larger square? This is a well known puzzle, and the answer is no. Using a linear algebraic approach, G\'abor Tardos and I answered the question of Florestan Brunck: What happens if the grasshoppers originally sit at the vertices of a regular n-gon $(n>4)$ ? For the proof, we need to establish some general results on linear transformations.

The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set $S$ in $\mathbb{R}^d$, then there are at most $2d$ points of $S$ whose convex hull contains the origin in the interior. B\'ar\'any, Katchalski and Pach proved the following quantitative version. Let $Q$ be a convex polytope in $\mathbb{R}^d$ containing the standard Euclidean unit ball $B$. Then there exist at most $2d$ vertices of $Q$ whose convex hull $Q^\prime$ satisfies \[ r B \subset Q^\prime \] with $r\geq d^{-2d}$. They conjectured that $r\geq c d^{-1/2}$ holds with a universal constant $c>0$. We show the first polynomial lower bound on $r$, and also present an upper bound. Joint work with Grigory Ivanov.

Given q-uniform hypergraphs (q-graphs) $F,G$ and $H$, where $G$ is a spanning subgraph of $F, G$ is called weakly H-saturated in $F$ if the edges in $E(F)\E(G)$ admit an ordering $e1,...,ek $ so that for all $i$ in $[k]$ the hypergraph $G \cup \{ e1,...,ei}\ $contains an isomorphic copy of $H$ which in turn contains the edge ei. The weak saturation number of $H$ in $F$ is the smallest size of an $H$-weakly saturated subgraph of $F$. Weak saturation was introduced by Bollobás in 1968, but despite decades of study our understanding of it is still limited. The main difficulty lies in proving lower bounds on weak saturation numbers, which typically withstands combinatorial methods and requires arguments of algebraic or geometric nature. In this talk we will describe how to determine exactly the weak saturation number of complete multipartite q-graphs in the directed setting, for any choice of parameters. This generalizes a theorem of Alon from 1985. Our proof combines the exterior algebra approach from the works of Kalai with the use of the colorful exterior algebra motivated by the recent work of Bulavka, Goodarzi and Tancer on the colorful fractional Helly theorem. D. Bulavka, M. Tyomkyn

Tverberg's theorem says that a set with sufficiently many points in $\mathbb{R}^d$ can always be partitioned into $m$ parts so that the $(m-1)$-simplex is the (nerve) intersection pattern of the convex hulls of the parts. In [1] the authors investigate how other simplicial complexes arise as nerve complexes once we have a set with sufficiently many points. In this paper we relate the theory of word-representable graphs [2] to a way of codifying $1$-skeletons of simplicial complexes to generate nerves. In particular, we show that every $2$-word-representable triangle-free graph, every circle graph, every outerplanar graph, and every bipartite graph could be induced as a nerve complex once we have a set with sufficiently many points in $\mathbb{R}^d$ for some $d$. [1] De Loera, J. A., Hogan, T. A., Oliveros, D., and Yang, D. ``Tverberg- Type Theorems with Altered Intersection Patterns (Nerves).” Discrete and Computational Geometry 65.3 (2021): 916-937. [2] Kitaev, Sergey, and Artem Pyatkin. ``On representable graphs.” Journal of automata, languages and combinatorics 13.1 (2008): 45-54.

Let $K\subset \mathbb{R}^n$ be a convex body, $n\geq 3$. We say that $K$ satisfies the \textit{Barker-Larman condition} (\textit{Montejano condition}) if there exists a sphere $B\subset \text{int} K$ such that for every suppor\-ting hyperplane $\Pi$ of $B$, the section $\Pi \cap K$ is a centrally symmetric set (a body of constant width). In this talk we are going to speak about the following results where, in both cases, $K$ is an $O$-symmetric convex body and $O\notin B$: 1) If $K$ is a strictly convex body and satisfies the Barker-Larman condition, then $K$ is an ellipsoid; 2) If $K$ satisfies the Montejano condition, then $K$ is a ball.

How many essentially distinct ways are there to arrange $n$ convex sets in $\mathbb{R}^d$? Here, `essentially distinct' means `with different intersection pattern'. We discuss this question both in the dimension $1$, where it amounts to counting the interval graphs, and in higher dimenions. Based on the joint works with Amzi Jeffs. Plain text abstract: How many essentially distinct ways are there to arrange n convex sets in R^d? Here, `essentially distinct' means `with different intersection pattern'. We discuss this question both in the dimension 1, where it amounts to counting the interval graphs, and in higher dimenions. Based on the joint works with Amzi Jeffs.

A pure $k$-dimensional simplicial complex is shellable if its facets can be ordered in such a way that each facet intersects the union of the previous ones in a non-empty union of $(k-1)$-dimensional simplices. Since shellable complexes can be built gradually, while controlling their topological properties, shellability is an important notion with a wide range of applications. Using the NP-hardness of planar rectilinear monotone 3-SAT, we show that the following problems are NP-complete. a) deciding whether a given simplicial d-ball is shellable (d>=3) b) deciding whether a given 3-complex embedded in $R^3$ is collapsible c) deciding whether a given 2-complex embedded in $R^3$ is shellable. This is a joint work with Martin Tancer