Schedule for: 19w5028 - Helly and Tverberg type Theorems

The classical Tverberg's theorem says that a set with sufficiently many points in $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. Motivated by questions from the performance of data classification algorithms such as multi-class logistic regression method, we investigated other version Tverberg. Our main results demonstrate that Tverberg's theorem is but a special case of a much more general situation. Given sufficiently many points, any tree or cycle, can also be induced by at least one partition of the point set. The proofs require a deep investigation of oriented matroids and order types. We also present new results on the distribution of simplicial complexes arising from the classification of data. (Joint work with Deborah Oliveros, Tommy Hogan, Dominic Yang (supported by NSF).)

The convex dimension of a k-uniform hypergraph is the smallest dimension d for which there is an injective mapping of its vertices into R^d such that the set of k-barycenters of all hyperedges is in convex position. We completely determine the convex dimension of complete k-uniform hypergraphs. This settles an open question by Halman, Onn and Rothblum, who solved the problem for complete graphs. We also provide lower and upper bounds for the extremal problem of estimating the maximal number of hyperedges of k-uniform hypergraphs on n vertices with convex dimension d. To prove these results we restate them in terms of affine projections of the hypersimplex that preserve its vertices. More generally, we study projections that preserve higher dimensional skeleta. In particular, we obtain a hypersimplicial generalization of the linear van Kampen-Flores theorem: for each n, k and i we determine onto which dimensions can the (n,k)-hypersimplex be linearly projected while preserving its i-skeleton.

The scissors congruence conjecture for the unimodular group is an analogue of Hilbert?s third problem, for the equidecomposability of polytopes. In this talk, we present a proof of this conjecture for polytopes naturally associated to graphs whose vertices have degree one or three. The key ingredient in the proof is the nearest neighbor interchange on graphs and a naturally arising piecewise unimodular transformation. We also discuss some Ehrhart quasi-polynomials results for this class of polytopes (joint work with C.G. Fernandes, J.C. de Pina and S. Robins).

What are the possible Venn diagrams we can draw with open sets in Euclidean space if all regions must be contractible? I will show that there is only one type of local obstruction that vanishes if and only if this is possible. If the regions of the diagram must be convex, this question is much more difficult, and stronger obstructions exist. In this case the intersection combinatorics are captured by convex neural codes, and I will present some recent progress towards understanding these codes. This is joint work with Aaron Chen and Anne Shiu.

In this talk I'll explain why finite Helly numbers exist for periodic and certain quasiperiodic sets in Euclidean space of any dimension though the bounds in the latter case seem to be extremely non-optimal. I'll also show that for a wider class of Meyer sets Helly numbers could be infinite.

We prove the following Helly-type result. Let $\mathcal{C}_1,\ldots,\mathcal{C}_{3d}$ be finite families of convex bodies in $\mathbb{R}^d$. Assume that for any colorful choice of $2d$ sets, $C_{i_k}\in \mathcal{C}_{i_k}$ for each $1\leq k\leq 2d$ with $1\leq i_1< \ldots < i_{2d}\leq 3d$, the intersection $\bigcap\limits_{k=1}^{2d} C_{i_k}$ contains an ellipsoid of volume at least 1. Then there is a color class $1\leq i \leq 3d$ such that $\bigcap\limits_{C\in \mathcal{C}_i} C$ contains an ellipsoid of volume at least $d^{-O(d^2)}$. Joint work with Gábor Damásdi and Viktória Földvári.

If every $k$-membered subfamily of a family of plane convex bodies has a line transversal, then we say that this family has property $T(k)$. We say that a family $\mathcal{F}$ has property $T-m$, if there exists a subfamily $\mathcal{G} \subset \mathcal{F}$ with $|\mathcal{F} - \mathcal{G}| \le m$ admitting a line transversal. In 2007, Heppes posed the problem whether there exists a convex body $K$ in the plane such that if $\mathcal{F}$ is a finite $T(3)$-family of disjoint translates of $K$, then $m=3$ is the smallest value for which $\mathcal{F}$ has property $T-m$. In this talk, we study this open problem {in terms of} finite $T(3)$-families of pairwise disjoint translates of a regular $2n$-gon $(n \ge 5)$. We find out that, for $5 \le n \le 34$, the family has property $T - 3$; for $n \ge 35$, the family has property $T - 2$. This is a joint work with Qingdan Du and Tudor Zamfirescu.

A few remarks on the history of geometry will lead to a novel approach to how we teach it (and what of it we do). In particular, conic curves and non euclidean geometries can be seen as a consequence of incidence geometry.

We will discuss several quantitative Helly theorems, where we characterize families of convex sets whose intersection has a large volume or diameter. The Helly numbers we obtain depend on the complexity of a ?witness set? that guarantees that the intersection is large. For example, our Helly numbers characterize families of convex sets that contain ellipsoids with large volume, or zonotopes with large diameter. The methods we describe work for a wide family of functions and witness sets. We will describe which results can be proven with purely geometric methods and which ones require a bit of topology.

An r-segment hypergraph H is a hypergraph whose edges consist of r consecutive integer points on line segments in ${\mathbb{R}}^2$. We will discuss some recent bounds on the chromatic numbers and covering numbers of r-segment hypergraphs, uncovering several interesting geometric properties in the process. Joint work with Deborah Oliveros and Chris O'Neill.

I will discuss the combinatorial relationship between the colorful Helly theorem and the fractional Helly theorem, and show some applications in abstract convexity and chi-boundedness of certain hypergraphs.

Radon's theorem is one of the cornerstones of convex geometry. It implies many of the key results in the area such as Helly's theorem and, as recently shown by Andreas Holmsen and Dong-Gyu Lee, also its more robust version, fractional Helly's theorem together with a colorful strengthening of Helly's theorem. Consequently, this yields an existence of weak epsilon nets and a (p,q)-theorem. We show that we can obtain these results even without assuming convexity, replacing it with very weak topological conditions. Moreover, using the recent result of myself and Gil Kalai, we manage to bring the fractional Helly number for open sets in the plane or on a surface down to three. This also settles a conjecture of Andreas Holmsen, Minki Kim, and Seunghun Lee about an existence of a (p,q)-theorem for open subsets of a surface.

In her recent result, Zuzana Patáková has shown that for a finite family $\mathcal F$ of sets in $\mathbb R^d$, one can use Betti numbers of intersections of subfamilies of $\mathcal F$, to bound the Radon's number of $\mathcal F$. The result has interesting consequences, some of them are easy or standard, other follow from a result of Holmsen and Lee. Let me name just few: variants of Helly's, Tverberg's, colorful and fractional Helly theorems, existence of weak $\varepsilon$-nets, $(p,q)$-theorems, \dots Nevertheless, the original bounds on Radon's number are too large to be widely applicable. We improve the situation in the plane and show how to obtain polynomial bounds. More generally the result extends to other two-dimensional (pseudo)manifolds.

TBA

We introduce and study a new class of extensions for the Borsuk--Ulam theorem. Our approach is based on the theory of Voronoi diagrams and Delaunay triangulations. One of our main results is as follows. \begin{thm}\label{corDln1} Let $S^m$ be a unit sphere in $R^{m+1}$ and let $f: S^m \to R^n$ be a continuous map. Then there are points $p$ and $q$ in $S^m$ such that \begin{itemize} \item $\|p-q\|\ge\sqrt{2\cdot\frac{m+2}{m+1}}$\/{\rm;} \item $f(p)$ and $f(q)$ lie on the boundary of a closed metric ball $B$ in $R^n$ whose interior does not meet $f(S^m)$. \end{itemize} \end{thm} Note that $\sqrt{2\cdot\frac{m+2}{m+1}}$ is the diameter of a regular simplex inscribed in $S^m$. Joint paper with Andrey Malyutin.

Let $K$ be a simplicial $k$-complex and $M$ be a closed PL $2k$-manifold. Our first aim during the talk is to describe an obstruction for embeddability of $K$ into $M$ via the intersection form on $M$. For description of the obstruction, we need a technical condition which is satisfied, in particular, either if $M$ is $(k-1)$-connected or if $K$ is the $k$-skeleton of $n$-simplex, for some $n$. Under the technical condition, if $K$ (almost) embeds in $M$, then our obstruction vanishes. In addition, if $M$ is $(k-1)$-connected and $k \geq 3$, then the obstruction is complete, that is, we get the reverse implication. Modulo a recent hard Lefschetz theorem of Adiprasito, a consequence of our results on the existence and completeness of the obstruction are very good bounds on the Helly number in a certain Helly type theorem where the ambient space is a (suitable) manifold. The details will be explained during the talk. The talk is based on a joint work with Pavel Paták.

In this work we prove that if there exists a point $p\in \mathbb{R}^n$ and a smooth convex body $M$ in $\mathbb{R}^n$, $n\geq 3$, contained in the interior of the unit ball of $\mathbb{R}^n$, such that $M$ looks centrally symmetric, and $p$ appears as the centre, from each point of $\mathbb{S}^{n-1}$, then $M$ is an sphere. Using this result we derived, straightaway, a well known characterization of the sphere due to S. Matsuura

The following is known as the geometric hypothesis of Banach: let V be an m-dimensional Banach space with unit ball B and suppose all n-dimensional subspaces of V are isometric (all the n-sections of B are affinely equivalent). In 1932, Banach conjectured that under this hypothesis V is a Hilbert space (the boundary of B is an ellipsoid). Gromow proved in 1967 that the conjecture is true for n=even and Dvoretzky derived the same conclusion under the hypothesis n=infinity. We prove this conjecture for all positive integers of the form n=4k+1, with the possible exception of 133. The ingredients of the proof are classical homotopic theory, irreducible representations of the orthogonal group and convex geometry

We discuss some classical problems of mathematical economics, in particular, 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. 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 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 odd and not a prime power, the counterexamples showing that the topological configuration space / test map scheme for a wide class of equipartition problems fails. This is applicable, for example, to building stronger counterexamples for the topological Tverberg conjecture (in another joint work with Sergey Avvakumov and Arkadiy Skopenkov). Joint work with Sergey Avvakumov

The set of all triangulations of a finite point set in the plane attains structure via flips: The graph, where two triangulations are adjacent if one can be obtained from the other by an elementary flip. This is an edge flip for full triangulations, or a bistellar flip for partial triangulations (where non-extreme points can be skipped). It is well-known (Lawson, 1972) that both, the edge flip graph and the bistellar flip graph are connected. For n the number of points and general position assumed, we show that the edge flip graph is (n/2 - 2)-connected and the bistellar flip graph is (n-3)-connected. Both bounds are tight. This matches the situation for regular triangulations (a subset of the partial triangulations), where (n-3)-connectivity was known through the secondary polytope (Gelfand, Kapranov, Zelevinsky, 1990) and Balinski's Theorem. We show that the edge flip graph can be covered by 1-skeletons of polytopes of dimension at least n/2-2 (products of associahedra). Similarly, the bistellar flip graph can be covered by 1-skeletons of polytopes of dimension at least n-3 (products of secondary polytopes). (covers joint research with Uli Wagner, IST Austria)

The Helly theorem in the title says the following. Assume $k < d+1$ and $F$ is a finite family of convex bodies, all contained in the Euclidean unit ball of $R^d$ with the property that every $k$-tuple of sets in $F$ has a point in common. Then there is a point $q$ in $R^d$ which is closer than $1/ \sqrt k$ to every set in $F$. This result has several colourful and fractional variants. Similar versions of Tverberg's theorem and some of their extensions are also established. This is joint work with Karim Adiprasito, Nabil Mustafa, and Tamás Terpai.