Schedule for: 16w5064 - Transversal, Helly and Tverberg type Theorems in Geometry, Combinatorics and Topology III

A welcome drink will be served at the hotel.

Let $k,d,\lambda\ge 1$ be integers with $d\ge \lambda$. Let $m(k,d,\lambda)$ be the maximum positive integer $n$ such that every set $X$ of $n$ points (not necessarily in general position) in $\mathbb{R}^{d}$ has the property that the convex hulls of all $k$-sets have a common transversal $(d-\lambda)$-plane (called \emph{Kneser Transversal}). It turns out that $m(k, d,\lambda)$ is strongly connected with other interesting problems, for instance, the chromatic number of Kneser hypergraphs and a discrete version of Rado's centerpoint theorem. In the same spirit, we introduce a natural discrete version $m^*$ of $m$ by considering the existence of \emph{complete Kneser transversals} (in which we ask, in addition, that the transversal $(d-\lambda)$-plane contains $(d-\lambda)+1$ points of $X$). In this Talk, we present results concerning the relation between $m$ and $m^*$ and give a number of lower and upper bounds of $m^*$ as well as the exact value in some cases. After introducing the notions of \emph{stability} and \emph{instability} for (complete) Kneser transversals we give a stability result that leads to a nice geometric properties for the existence of (complete) Kneser transversals. We end by presenting some computational results (closely related to the stability and unstability notions). (This is a joint work with J. Chappelon, L. Martinez, L. Montejano and L.P. Montejano)

We examine Gromov's method of selecting a point ``heavily covered'' by simplices chosen from a given finite point sets, in order to understand the dependence of the heavily covered point on parameters. There is no continuous dependence in this problem, but it is possible to utilize the ``homological continuous dependence'' of the heavily covered point, if we follow Gromov's approach to the problem. This allows us to infer some corollaries in a usual way. We also give an elementary argument to prove the simplest of these corollaries in the planar case and discuss other approaches and some open problems in the area.

Pach's selection theorem asserts that for any positive integer $d$ there exists a constant $c_d > 0$ such that for any positive integer $n$ and any finite sets $X_1, ..., X_{d+1} in \mathbb{R}^d$ each with $n$ points there exist disjoint subsets $Z_1, ..., Z_{d+1}, Z_i$ is a subset of $X_i$ and a point $z$ such that $z$ belongs to any rainbow $(Z_1, ..., Z_{d+1})$-simplex; that is, a convex hull of points $z_1, ..., z_{d+1}$ where $z_i$ belongs to $Z_i$. Although the topological method is a valuable tool for improving the bounds for certain selection theorems (introduced by Gromov), we prove that Pach's theorem does not admit a topological extension. Joint work with Imre B\'ar\'any, Roy Meshulam and Eran Nevo.

The combinatorics of missing faces of a simplicial complex give nontrivial information about whether it is embeddable into d-space, and more generally whether every continuous map to d-space exhibits a point of r-fold intersection. This can be used to relate intersection patterns of finite sets as in Kneser's conjecture to intersection patterns of convex sets as in Tverberg's theorem and its continuous generalizations. We will present a theorem that is a common generalization of results from Tverberg-type theory and lower bounds for chromatic numbers of uniform intersection hypergraphs, extending work of Sarkaria.

The KKM (Knaster - Kuratowski - Mazurkiewicz) theorem has many applications in combinatorics, algorithms, game theory and mathematical economics. In this talk we consider generalizations of Gale's colored KKM lemma and Shapley's KKMS theorem. It is shown that space and covers can be much more general and the boundary KKM rules can be substituted by more weaker boundary assumptions.

Colorful Tverberg theorem states that given a set of $(r-1)(d+1)+1$ points in $\mathbb{R}^d$ divided into $m$ color classes of size at most $(r-1)$, there exist $r$ rainbow simplices whose intersection is non-empty. Simplex is called rainbow, if all its vertices are points of different colors. Here we prove the same bounds for matroidal version of the problem. Since a simplex is the convex hull of its vertices the conclusion of the original colorful Tverberg can be restated as "The intersection of convex hulls of some r rainbow sets is non-empty". In the matroidal version, we replace convex hulls with any (matroidal) closure operator (e.g. affine hulls). The advantage of the "affine closure" version is that it is valid even for fields for which convex hulls are not defined, we may weaken the assumptions and assume that one of the color classes has size at most r and the remaining have size at most r-1, and that the rainbow sets can be found algorithmically. On the other hand, the conclusions of the theorem are weaker. We show that the theorem is tight and present some application of it.

We introduce the notion of \textit{intersection depth} for a finite family of convex sets $\mathcal{F}$ in $\mathbb{R}^d$. Specifically, we say that a point $p$ has \textit{intersection depth $m$ with respect to $\mathcal{F}$} if every hyperplane that contains $p$ intersects at least $m$ sets of $\mathcal{F}$. We study some nice properties of intersection depth and we relate it to other notions of depth in the literature. By imposing additional intersection hypothesis to the family $\mathcal{F}$, we show how to prove sharp centerpoint theorems for intersection depth. These results can be thought of as a refinement that interpolates between the classical Rado's centerpoint theorem and Helly's theorem. Finally, we use this result to get a new Helly-type theorem for fractional transversal hyperplanes that cannot be obtained from the well-studied $T(k)$ hypothesis.

B\'ar\'any, Katchalski and Pach proved the following quantitative form of Helly's theorem: If the intersection of a family of convex sets in $\mathbb{R}^d$ is of volume one, then the intersection of some subfamily of at most $2d$ members is of volume at most some constant $v(d)$. They gave the bound $v(d)\leq d^{2d2}$, and conjectured that $v(d)\leq d^{cd}$. We confirmed it. We discuss the proof and further results.

This year we celebrate 50 year of the lovely theorem of Helge Tverberg! Let $a_{1},\ldots,a_{n}$ be points in $\mathbb{R}^{d}$. If the number of points $n$ satisfies $n >(d+1)(m-1)$, then they can be partitioned into $m$ disjoint parts $A_{1},\ldots,A_{m}$ in such a way that the $m$ convex hulls $Conv A_1, \ldots, Conv A_m$ have a point in common. Over the years many generalizations and extensions, including colorful, fractional, and topological versions, have been developed and are a bounty for discrete geometers. My talk will discusses yet another fascinating way to interpret Tverberg's theorem, now with a view toward number theory, lattices, integer programming, all things discrete not continuous nor topological. Given a discrete set $S$ of $\mathbb{R}^d$ (e.g., a lattice, or the Cartesian product of the prime numbers), we study the number of points of $S$ needed to guarantee the existence of an $m$-partition of the points $A_{1},\ldots,A_{m}$ such that the intersection of the $m$ convex hulls of the parts contains at least $k$ points of $S$. The proofs of the main results require new quantitative integer versions of Helly's and Carath\'eodory's theorems. Joint work with subsets of the following wonderful people Reuben La Haye, David Rolnick, and Pablo Soberon, Frederic Meunier and Nabil Mustafa.

A brief review of classical transversal results for finite families of ovals in the plane, and the recent developments that focus on weakening the disjoint condition in these results. We present these weakenings in terms of phi-distjoint, and conclude with a list of research problems that follow from this generalization. (Joint work with Heppes Aladar.)

Suppose $A$ and $P$ are sets in $\mathbb{R}^d$ such that every convex set containing α-fraction of points P contains at least $(\alpha -\epsilon)$-fraction of points of $A$, for every $\alpha$. In such a case, set $A$ is called a one-sided $\epsilon$-approximant to $P$. We show that every $P$ admits a one-sided $\epsilon$-approximant of size depending only on $\epsilon$ and on $d$. (Joint work with Gariel Nivasch.)

Consider a finite dimensional, real normed space. For a given set of vectors of norm at most 1, which sum to 0, we would like to select a k-element subset with small norm. We provide sharp estimates. We also prove consequences regarding Steinitz's theorem. This is a joint work with Imre Barany and Victor Grinberg.

We show how the probabilistic method can be applied to obtain robust versions of this Tverberg's theorem. In particular, given positive integers $r, d, t$, we study the number of points needed in $\mathbb{R}^d$ to guarantee the existence of a partition of them into r parts such that, even after any t points are removed, the convex hulls of what is left in each part have non-empty intersection.

A parallelogram inscribed in a given convex disk $K$ in the plane is {\it extensive} if each of its sides is at least as long as one-half of the affine diameter of $K$ parallel to the side. Such a parallelogram generates a double-lattice packing of the plane that mixes translates of $K$ with translates of $-K$. The smaller the area of the parallelogram, the denser the packing. The densest double-lattice packing of the the regular pentagon has density $(5-\sqrt5)/3=0.92131\ldots$, which is conjectured to be the highets density among all packings with the pentagon's congruent copies. Recent developments will be discussed along with various questions and conjectures that arise naturally.

The Dvoretzky-Rogers lemma states the existence of a simplex of relatively large volume in a John decomposition of the identity. This theorem was the key ingredient in the recent proof by M. Nasz\'odi of a quantitative version of Helly's theorem which had been conjectured originally by B\'ar\'any, Katchalski and Pach. In this talk we present a new measure theoretic version of the Dvoretzky-Rogers lemma which provides information about the distribution of isotropic measures. This result is joint with K.J. B\"or\"oczky (Budapest) and D. Hug (Karlsruhe).

Let $D(d,k)$ denote the largest possible diameter over all polytopes which vertices are drawn from $\{ 0,1,...,k\}^d$. In 1989, Naddef showed that $D(d,1)=d$. This result was generalized in 1992 by Kleinschmidt and Onn who proved that $D(d,k) \leq kd$, before Del Pia and Michini tightened in 2016 the inequality to $D(d,k) \leq (k-1/2)d$ for $k\geq 2$. We show that $D(d,k) \leq (k-2/3)d$ for $k \geq 3$. In addition, we show that $D(4,3)=8$, which substantiates the conjecture stating that $D(d,k) \leq (k+1)d/2$, and is achieved by a Minkowski sum of lattice vectors. Based on a joint work with Lionel Pournin, Universit\'e Paris 13.

In this talk we give an asymptotically tight bound for the tolerated Tverberg Theorem when the dimension and the size of the partition are fixed. To achieve this, we study certain partitions of order-type homogeneous sets and use a generalization of the Erd\''os-Szekeres theorem. Joint Work with Edgardo Roldan.

We show that for every $d,r,N$ positive integers there exists $n = n(d,r,N)$ such that Any sequence $p$ in $R^d$ of length $n$ has a subsequence $p’$ of length $N$ such that Every subsequence of $p’$ of length $T(d,r) = (r-1)(d+1)+1$ has identical Tverberg partitions, namely the “rainbow” – partitions. A partition (or coloring) of the first $T(d,r)$ integers into $r$ parts (with $r$ colors) is called rainbow If every color appears exactly once in each of the following $r$-tuples: $(1, …., r), (r, …, 2r-1), (2r-1, …, 3r-2), …., ((d-1)r-(d-2), …, d r-(d-1))$.

A {\em pseudocircle} is an oriented Jordan closed curve on some surface. A finite collection of pseudocircles that pairwise cross in exactly two points is an {\em arrangement of pseudocircles}, and it is {\em strict} if each pseudocircle is a separating curve on the host surface. Following Linhart and Ortner, the combinatorial properties of an arrangement of pseudocircles are encoded in an {\em intersection matrix}, in which each row corresponds to a pseudocircle, and the entries of the row give the cyclic order of its (signed) intersections with the other pseudocircles in the arrangement. Ortner proved that an arrangement of pseudocircles (given as an intersection matrix) can be embedded into the sphere if and only if each of its subarrangements of size four can be embedded in the sphere. In this work we present an extended result, where it was shown that an arrangement of pseudocircles (given as an intersection matrix) is embeddable into the compact orientable surface $S_g$ of genus $g$ if and only if each of its subarrangements of size $4(g+1)$ can be embedded in $S_g$. Joint work with Edgardo Roldan and Gelasio Salazar.

A geometric join is the union of all colorful simplices spanned by a colored point set in the d-dimensional space. For a given dimension, how many colors are needed to guarantee that the geometric join will be contractible? I will explain some of the bounds (and conjectures) obtained with Imre Barany and Roman Karasev.

Three measures of non-convexity of a set in $R^d$ will be discussed. The invisibility graph $I(X)$ of a set $X \subseteq R^d$ is a (possibly infinite) graph whose vertices are the points of $X$ and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in $X$. We consider the following three parameters of a set $X$: the clique number $\omega(I(X))$, the chromatic number $\chi(I(X))$ and the minimum number $\gamma(X)$ of convex subsets of $X$ that cover $X$. Observe that $\omega(X) \leq \chi(X) \leq \gamma(X)$ for any set $X$, where $\omega(X):=\omega(I(X))$ and $\chi(X)=\chi(I(X))$. Here is a sample of results comparing the above three parameters: 1. Let $X \subseteq R^2$ be a planar set with $\omega(X)=\omega < \infty$ and with no one-point holes. Then $\gamma(X) \leq O(\omega^4)$. 2. For every planar set $X$, $\gamma(X)$ can be bounded in terms of $\chi(X)$. 3. There are sets $X$ in $R^5$ with $\chi(X)=3$, but $\gamma(X)$ arbitrarily lar ge. The talk is based on joint papers with J. Cibulka, M. Korbel\'a\v r, M. Kyn\v cl, J. Matou\v sek, V. M\'esz\'aros, and R. Stola\v r.

We present a simple and fairly elementary proof of Gromov?s Topological Overlap Theorem. Let $X$ is a finite $d$-dimensional simplicial complex. Informally, the theorem states that if $X$ has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of $X$) then $X$ has the following topological overlap property: for every continuous map from $X$ to $d$-dimensional Euclidean space, there exists an image point p contained in the images of a positive fraction $\mu>0$ of the $d$-simplices of $X$. More generally, the conclusion holds if d is replaced by any $d$-dimensional piecewise-linear manifold $M$, with a constant $\mu$ that depends only on d and on the expansion properties of $X$, but not on $M$. Joint work with Dominic Dotterrer and Tali Kaufman.