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]

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]

We study properties of the realizations of groups as the combinatorial automorphism group of a convex polytope. We show that for any non-abelian group G with a central involution there is a centrally symmetric polytope with G as its combinatorial automorphisms. We show that for each integer n, there are groups that cannot be realized as the combinatorial automorphisms of convex polytopes of dimension at most n. We also give an optimal lower bound for the dimension of the realization of a group as the group of isometries that preserves a convex polytope. [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]

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 introduce the partition function of edge-colored graph homomorphisms, of which the usual partition function of graph homomorphisms is a specialization, and present an efficient algorithm to approximate it in a certain domain. Corollaries include effcient algorithms for computing weighted sums approximating the number of k-colorings and the number of independent sets in a graph, as well as an effcient procedure to distinguish pairs of edge-colored graphs with many color-preserving homomorphisms G → H from pairs of graphs that need to be substantially modified to acquire a color-preserving homomorphism G → H. [ABSTRACT FROM AUTHOR]

Given a finite set X of points in $$R^n$$ and a family F of sets generated by the pairs of points of X, we determine volumetric and structural conditions for the sets that allow us to guarantee the existence of a positive-fraction subfamily $$F'$$ of F for which the sets have non-empty intersection. This allows us to show the existence of weak epsilon-nets for these families. We also prove a topological variation of the existence of weak epsilon-nets for convex sets. [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]

We study nested partitions of R obtained by successive cuts using hyperplanes with fixed directions. We establish the number of measures that can be split evenly simultaneously by taking a partition of this kind and then distributing the parts among k sets. This generalises classical necklace splitting results and their more recent high-dimensional versions. With similar methods we show that in the plane, for any t measures there is a path formed only by horizontal and vertical segments using at most t - 1 turns that splits them by half simultaneously, and optimal masspartitioning results for chessboard colourings of R using hyperplanes with fixed directions. [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]

The coloured Tverberg theorem was conjectured by Bárány, Lovász and Füredi [4] and asks whether for any d+1 sets (considered as colour classes) of k points each in ℝ there is a partition of them into k colourful sets whose convex hulls intersect. This is known when d=1;2 [5] or k+1 is prime [7]. In this paper we show that ( k−1) d+1 colour classes are necessary and sufficient if the coefficients in the convex combination in the colourful sets are required to be the same in each class. This result is actually a generalisation of Tverberg's classic theorem on the intersection of convex hulls [27]. We also examine what happens if we want the convex hulls of the colourful sets to intersect even if we remove any r of the colour classes, and its relation to other colourful variants of Tverberg's theorem. We investigate the relation of the case k=2 and the Gale transform, obtaining a variation of the coloured Radon theorem. We then show applications of these results to purely combinatorial problems. [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]