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

Beginning on Sunday, June 4 and ending Friday June 9, 2023

All times in Oaxaca, Mexico time, CDT (UTC-5).

Sunday, June 4
14:00 - 23:59 Check-in begins (Front desk at your assigned hotel)
19:30 - 22:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
20:30 - 21:30 Informal gathering (Hotel Hacienda Los Laureles)
Monday, June 5
07:30 - 09:00 Breakfast (Restaurant Hotel Hacienda Los Laureles)
09:35 - 09:50 Introduction and Welcome (Conference Room San Felipe)
09:50 - 10:30 Jorge Ramirez Alfonsin: Around the vertices of projective polytopes
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.
(Hotel Hacienda Los Laureles)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:40 Gergely Ambrus: Quantitative Helly-type theorems via sparse approximation.
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$.
(Hotel Hacienda Los Laureles)
11:40 - 12:20 Leonardo Ignacio Martínez Sandoval: Representing orders and pre-orders as orderings of pairwise Euclidean distances
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)
13:20 - 13:30 Group Photo (Hotel Hacienda Los Laureles)
13:30 - 15:00 Lunch (Restaurant Hotel Hacienda Los Laureles)
15:20 - 16:00 Deborah Oliveros: Problem Sesión (Hotel Hacienda Los Laureles)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:10 Nikola Sadovek: Iterated convex partitions
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ć.)
(Hotel Hacienda Los Laureles)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Tuesday, June 6
07:30 - 09:00 Breakfast (Restaurant Hotel Hacienda Los Laureles)
09:50 - 10:30 Zuzana Patáková: On Radon, fractional Helly and (p,q)-type theorems
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.
(Hotel Hacienda Los Laureles)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:40 Pavle Blagojevic: Many partitions of mass assignments
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.)
(Hotel Hacienda Los Laureles)
11:40 - 12:20 Attila Por (Hotel Hacienda Los Laureles)
13:30 - 15:00 Lunch (Restaurant Hotel Hacienda Los Laureles)
15:20 - 16:00 Florian Frick: Hyperplane partitions and transversals
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.
(Hotel Hacienda Los Laureles)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:10 Andrew Newman: Linear embeddings of random complexes
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.
(Hotel Hacienda Los Laureles)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Wednesday, June 7
07:30 - 09:00 Breakfast (Restaurant Hotel Hacienda Los Laureles)
09:50 - 10:30 Oleg Musin: Quantitative Sperner type lemmas
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)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:40 Edgardo Roldan-Pensado (Hotel Hacienda Los Laureles)
11:40 - 12:20 Janos Pach: Geometric applications of the linear algebra method
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.
(Hotel Hacienda Los Laureles)
12:30 - 13:30 Lunch (Restaurant Hotel Hacienda Los Laureles)
13:30 - 17:30 Free Afternoon (Monte Albán Tour) (Oaxaca)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Thursday, June 8
07:30 - 09:00 Breakfast (Restaurant Hotel Hacienda Los Laureles)
09:50 - 10:30 Marton Naszodi: Quantitative Steinitz theorems
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.
(Hotel Hacienda Los Laureles)
10:30 - 11:00 Coffee Break (Conference Room San Felipe)
11:00 - 11:40 Martin Tancer: Weak saturation of multipartite hypergraphs
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
(Hotel Hacienda Los Laureles)
11:40 - 12:20 Antonio de Jesús Torres: From word representable graphs to Tverberg type results
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.
(Hotel Hacienda Los Laureles)
13:30 - 15:00 Lunch (Restaurant Hotel Hacienda Los Laureles)
15:20 - 16:00 Efren Morales Amaya: On Baker-Larman Conjecture relative to a convex body with centrally symmetric sections
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.
(Hotel Hacienda Los Laureles)
16:00 - 16:30 Coffee Break (Conference Room San Felipe)
16:30 - 17:10 Boris Bukh: Enumeration of interval graphs and d-representable complexes
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.
(Hotel Hacienda Los Laureles)
17:10 - 17:50 Pablo Soberón: "The central transversal theorem revisited" (Hotel Hacienda Los Laureles)
19:00 - 21:00 Dinner (Restaurant Hotel Hacienda Los Laureles)
Friday, June 9
07:30 - 09:00 Breakfast (Restaurant Hotel Hacienda Los Laureles)
09:20 - 10:00 Ricardo Strausz: How do 9 points look like in E^3? (Hotel Hacienda Los Laureles)
10:00 - 10:40 Pavel Patak: Shellability is hard even for balls
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
(Hotel Hacienda Los Laureles)
10:40 - 11:10 Coffee Break (Conference Room San Felipe)
12:00 - 14:00 Lunch (Restaurant Hotel Hacienda Los Laureles)