Search

We use recent extensions of the Borsuk–Ulam theorem for Stiefel manifolds to generalize the ham sandwich theorem to mass assignments. A k-dimensional mass assignment continuously imposes a measure on each k-dimensional affine subspace of R d . Given a finite collection of mass assignments of different dimensions, one may ask if there is some sequence of affine subspaces S k - 1 ⊂ S k ⊂ ... ⊂ S d - 1 ⊂ R d such that S i bisects all the mass assignments on S i + 1 for every i. We show it is possible to do so whenever the number of mass assignments of dimensions (k , ... , d) is a permutation of (k , ... , d) . We extend previous work on mass assignments and the central transversal theorem. We also study the problem of halving several families of (d - k) -dimensional affine spaces of R d using a (k - 1) -dimensional affine subspace contained in some translate of a fixed k-dimensional affine space. For k = d - 1 , there results can be interpreted as dynamic ham sandwich theorems for families of moving points. [ABSTRACT FROM AUTHOR]

We generalize the Yao–Yao partition theorem by showing that for any smooth measure in R d there exist equipartitions using (t + 1) 2 d - 1 convex regions such that every hyperplane misses the interior of at least t regions. In addition, we present tight bounds on the smallest number of hyperplanes whose union contains the boundary of an equipartition of a measure into n regions. We also present a simple proof of a Borsuk–Ulam type theorem for Stiefel manifolds that allows us to generalize the central transversal theorem and prove results bridging the Yao–Yao partition theorem and the central transversal theorem. [ABSTRACT FROM AUTHOR]

Many results about mass partitions are proved by lifting |$\mathds {R}^d$| to a higher-dimensional space and dividing the higher-dimensional space into pieces. We extend such methods to use lifting arguments to polyhedral surfaces. Among other results, we prove the existence of equipartitions of |$d+1$| measures in |$\mathds {R}^d$| by parallel hyperplanes and of |$d+2$| measures in |$\mathds {R}^d$| by concentric spheres. For measures whose supports are sufficiently well separated, we prove results where one can cut a fixed (possibly different) fraction of each measure either by parallel hyperplanes, concentric spheres, convex polyhedral surfaces of few facets, or convex polytopes with few vertices. [ABSTRACT FROM AUTHOR]

We study the existence of fair distributions when we have more guests than pieces to allocate, focusing on envy-free distributions among those who receive a piece. The conditions on the demand from the guests can be weakened from those of classic cake-cutting and rent-splitting results of Stromquist, Woodall, and Su. We extend existing variations of the cake-cutting problem with secretive guests and those that resist the removal of any sufficiently small set of guests. [ABSTRACT FROM AUTHOR]

Mass partition problems describe the partitions we can induce on a family of measures or finite sets of points in Euclidean spaces by dividing the ambient space into pieces. In this survey we describe recent progress in the area in addition to its connections to topology, discrete geometry, and computer science. [ABSTRACT FROM AUTHOR]

For a finite set of S points in the plane and a graph with vertices on S, consider the disks with diameters induced by the edges. We show that for any odd set S, there exists a Hamiltonian cycle for which these disks share a point, and for an even set S, there exists a Hamiltonian path with the same property. We discuss high-dimensional versions of these theorems and their relation to other results in discrete geometry. [ABSTRACT FROM AUTHOR]

We prove an extension of a ham sandwich theorem for families of lines in the plane by Dujmović and Langerman. Given two sets A, B of n lines each in the plane, we prove that it is possible to partition the plane into r closed convex regions so that the following holds. For each region C of the partition there is a subset of c r n 1 / r lines of A whose pairwise intersections are in C, and the same holds for B. In this statement c r only depends on r. We also prove that the dependence on n is optimal. For a single set A of n lines, we prove that there exists a partition of the plane into r parts using r - 1 vertical lines such that each region contains the pairwise intersections of a set of n 1 / r lines of A. The value n 1 / r is optimal. [ABSTRACT FROM AUTHOR]

A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in Rd given some information on the diameter of the intersection of all sufficiently small subfamilies. We prove fractional and colorful versions of a long-standing conjecture by B\'ar\'any, Katchalski, and Pach. We also show that a Minkowski norm admits an exact Helly-type theorem for diameter if and only if its unit ball is a polytope and prove a colorful version for those that do. Finally, we prove Helly-type theorems for the property of "containing k colinear integer points. [ABSTRACT FROM AUTHOR]

This survey presents an overview of the advances around Tverberg's theorem, focusing on the last two decades. We discuss the topological, linear-algebraic, and combinatorial aspects of Tverberg's theorem and its applications. The survey contains several open problems and conjectures. [ABSTRACT FROM AUTHOR]

We prove a Tverberg type theorem: Given a set A⊂Rd in general position with |A|=(r-1)(d+1)+1 and k∈{0,1,…,r-1}, there is a partition of A into r sets A1,…,Ar (where |Aj|≤d+1 for each j) with the following property. There is a unique z∈⋂j=1raffAj and it can be written as an affine combination of the element in Aj: z=∑x∈Ajα(x)x for every j and exactly k of the coefficients α(x) are negative. The case k=0 is Tverberg’s classical theorem. [ABSTRACT FROM AUTHOR]

Abstract: We prove a common generalization of the Ham Sandwich theorem and Alon's Necklace Splitting theorem. Our main results show the existence of fair distributions of m measures in R d among r thieves using roughly m r / d convex pieces, even in the cases when m is larger than the dimension. The main proof relies on a construction of a geometric realization of the topological join of two spaces of partitions of R d into convex parts, and the computation of the Fadell–Husseini ideal valued index of the resulting spaces. [ABSTRACT FROM AUTHOR]

We show quantitative versions of classical results in discrete geometry, where the size of a convex set is determined by some non-negative function. We give versions of this kind for the selection theorem of Bárány, the existence of weak epsilon-nets for convex sets and the ( p , q ) theorem of Alon and Kleitman. These methods can be applied to functions such as the volume, surface area or number of points of a discrete set. We also give general quantitative versions of the colorful Helly theorem for continuous functions. [ABSTRACT FROM AUTHOR]

We consider a refinement of the partition function of graph homomorphisms and present a quasi-polynomial algorithm to compute it in a certain domain. As a corollary, we obtain quasi-polynomial algorithms for computing partition functions for independent sets, perfect matchings, Hamiltonian cycles and dense subgraphs in graphs as well as for graph colorings. This allows us to tell apart in quasi-polynomial time graphs that are sufficiently far from having a structure of a given type (i.e., independent set of a given size, Hamiltonian cycle, etc.) from graphs that have sufficiently many structures of that type, even when the probability to hit such a structure at random is exponentially small. [ABSTRACT FROM AUTHOR]

In this paper we study N( k), the smallest positive integer such that any nice measure μ in $\mathbb{R}^{d}$ can be partitioned into N( k) convex parts of equal measure so that every hyperplane avoids at least k of them. A theorem of Yao and Yao states that N(1)≤2. Among other results, we obtain the bounds N(2)≤3⋅2 and N(1)≥ C⋅2 for some constant C. We then apply these results to a problem on the separation of points and hyperplanes. [ABSTRACT FROM AUTHOR]

We will prove the following generalisation of Tverberg's Theorem: given a set S⊂ℝ of ( r+1)( k−1)( d+1)+1 points, there is a partition of S in k sets A, A,..., A such that for any C⊂ S of at most r points, the convex hulls of A\ C, A\ C,..., A\ C are intersecting. This was conjectured first by Natalia García-Colín (Ph.D. thesis, University College of London, ). [ABSTRACT FROM AUTHOR]

Given a finite family $\mathcal{F}$ of convex sets in ℝ, we say that $\mathcal{F}$ has the ( p, q) property if for any p convex sets in $\mathcal{F}$ there are at least r q-tuples that have nonempty intersection. The piercing number of $\mathcal{F}$ is the minimum number of points we need to intersect all the sets in $\mathcal{F}$. In this paper we will find some bounds for the piercing number of families of convex sets with ( p, q) properties. [ABSTRACT FROM AUTHOR]

Tverberg's theorem bounds the number of points R d needed for the existence of a partition into r parts whose convex hulls intersect. If the points are colored with N colors, we seek partitions where each part has at most one point of each color. In this manuscript, we bound the number of color classes needed for the existence of partitions where the convex hulls of the parts intersect even after any set of t colors is removed. We prove asymptotically optimal bounds for t when r ≤ d + 1 , improve known bounds when r > d + 1 , and give a geometric characterization for the configurations of points for which t = N − o (N). [ABSTRACT FROM AUTHOR]

We show that for any convex set K in R d and any finite family F of convex sets in R d , if the intersection of every sufficiently small subfamily of F contains an isometric copy of K of volume 1, then the intersection of the whole family contains an isometric copy of K scaled by a factor of (1 − ε) , where ε is positive and fixed in advance. Unless K is very similar to a disk, the shrinking factor is unavoidable. We prove similar results for affine copies of K. We show how our results imply the existence of randomized algorithms that approximate the largest copy of K that fits inside a given polytope P whose expected runtime is linear in the number of facets of P. [ABSTRACT FROM AUTHOR]

In 2011 at an Oberwolfach workshop in Discrete Geometry, V. Dol’nikov posed the following problem. Consider three non-empty families of translates of a convex compact set K in the plane. Suppose that every two translates from different families have a point of intersection. Is it always true that one of the families can be pierced by a set of three points? A result by R.N. Karasev from 2000 gives, in fact, an affirmative answer to the “monochromatic” version of the problem above. That is, if all the three families in the problem coincide. In the present paper we solve Dol’nikov’s problem positively if K is either centrally symmetric or a triangle, and show that the conclusion can be strengthened if K is a Euclidean disk. We also confirm the conjecture if we are given four families satisfying the conditions above. [ABSTRACT FROM AUTHOR]

We prove several exact quantitative versions of Helly's and Tverberg's theorems, which guarantee that a finite family of convex sets in R d has a large intersection. Our results characterize conditions that are sufficient for the intersection of a family of convex sets to contain a "witness set" which is large under some concave or log-concave measure. The possible witness sets include ellipsoids, zonotopes, and H -convex sets. Our results show that several new optimization problems can be solved with algorithms for LP-type problems. We obtain colorful and fractional variants of all our Helly-type theorems. [ABSTRACT FROM AUTHOR]

This paper presents a new variation of Tverberg's theorem. Given a discrete set S of $$\mathbb {R}^{d}$$ , we study the number of points of S needed to guarantee the existence of an m-partition of the points 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 versions of Helly's and Carathéodory's theorems. [ABSTRACT FROM AUTHOR]

We prove variations of Carathéodory's, Helly's and Tverberg's theorems where the sets involved are measured according to continuous functions such as the volume or diameter. Among our results, we present continuous quantitative versions of Lovász's colorful Helly's theorem, Bárány's colorful Carathéodory's theorem, and the colorful Tverberg's theorem. [ABSTRACT FROM AUTHOR]

In this paper, we study the number of compact sets needed in an infinite family of convex sets with a local intersection structure to imply a bound on its piercing number, answering a conjecture of Erdős and Grünbaum. Namely, if in an infinite family of convex sets in $$\mathbb {R}^d$$ we know that out of every $$p$$ there are $$q$$ which are intersecting, we determine if having some compact sets implies a bound on the number of points needed to intersect the whole family. We also study variations of this problem. [ABSTRACT FROM AUTHOR]