BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
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 theorem, Bárány's colorful Carathéodory's theorem, and the colorful Tverberg theorem.
This paper presents a new variation of Tverberg's theorem. Given a discrete set S of Rd, 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.
We solve a problem in the combinatorics of polyhedra motivated by the network simplex method. We show that the Hirsch conjecture holds for the diameter of the graphs of all network-flow polytopes, in particular the diameter of a network-flow polytope for a network with n nodes and m arcs is never more than m+n−1. A key step to prove this is to show the same result for classical transportation polytopes.
The scenario approach developed by Calafiore and Campi to attack chance-constrained convex programs utilizes random sampling on the uncertainty parameter to substitute the original problem with a representative continuous convex optimization with N convex constraints which is a relaxation of the original. Calafiore and Campi provided an explicit estimate on the size N of the sampling relaxation to yield high-likelihood feasible solutions of the chance-constrained problem. They measured the probability of the original constraints to be violated by the random optimal solution from the relaxation of size N. This paper has two main contributions. First, we present a generalization of the Calafiore-Campi results to both integer and mixed-integer variables. In fact, we demonstrate that their sampling estimates work naturally for variables restricted to some subset S of Rd. The key elements are generalizations of Helly's theorem where the convex sets are required to intersect S⊂Rd. The size of samples in both algorithms will be directly determined by the S-Helly numbers. Motivated by the first half of the paper, for any subset S⊂Rd, we introduce the notion of an S-optimization problem, where the variables take on values over S. It generalizes continuous, integer, and mixed-integer optimization. We illustrate with examples the expressive power of S-optimization to capture sophisticated combinatorial optimization problems with difficult modular constraints. We reinforce the evidence that S-optimization is "the right concept" by showing that the well-known randomized sampling algorithm of K. Clarkson for low-dimensional convex optimization problems can be extended to work with variables taking values over S.
We study S-convex sets, which are the geometric objects obtained as the intersection of the usual convex sets in Rd with a proper subset S⊂Rd. We contribute new results about their S-Helly numbers. We extend prior work for S=Rd, Zd, and Zd−k×Rk; we give sharp bounds on the S-Helly numbers in several new cases. We considered the situation for low-dimensional S and for sets S that have some algebraic structure, in particular when S is an arbitrary subgroup of Rd or when S is the difference between a lattice and some of its sublattices. By abstracting the ingredients of Lovász method we obtain colorful versions of many monochromatic Helly-type results, including several colorful versions of our own results.
This paper presents sixteen quantitative versions of the classic Tverberg, Helly, & Caratheodory theorems in combinatorial convexity. Our results include measurable or enumerable information in the hypothesis and the conclusion. Typical measurements include the volume, the diameter, or the number of points in a lattice.
This paper studies systems of polynomial equations that provide information about orientability of matroids. First, we study systems of linear equations over GF(2), originally alluded to by Bland and Jensen in their seminal paper on weak orientability. The Bland-Jensen linear equations for a matroid M have a solution if and only if M is weakly orientable. We use the Bland-Jensen system to determine weak orientability for all matroids on at most nine elements and all matroids between ten and twelve elements having rank three. Our experiments indicate that for small rank, about half the time, when a simple matroid is not orientable, it is already non-weakly orientable. Thus, about half of the small simple non-orientable matroids of rank three are not representable over fields having order congruent to three modulo four. For binary matroids, the Bland-Jensen linear systems provide a practical way to check orientability. Second, we present two extensions of the Bland-Jensen equations to slightly larger systems of non-linear polynomial equations. Our systems of polynomial equations have a solution if and only if the associated matroid M is orientable. The systems come in two versions, one directly extending the Bland-Jensen system for GF(2), and a different system working over other fields. We study some basic algebraic properties of these systems. Finally, we present an infinite family of non-weakly-orientable matroids, with growing rank and co-rank. We conjecture that these matroids are minor-minimal non-weakly-orientable matroids.
The cyclic polytope C(n,d) is the convex hull of any n points on the moment curve (t,t2,...,td):t∈R in Rd. For d′>d, we consider the fiber polytope (in the sense of Billera and Sturmfels) associated to the natural projection of cyclic polytopes π:C(n,d′)→C(n,d) which "forgets" the last d′−d coordinates. It is known that this fiber polytope has face lattice indexed by the coherent polytopal subdivisions of C(n,d) which are induced by the map π. Our main result characterizes the triples (n,d,d′) for which the fiber polytope is canonical in either of the following two senses: - all polytopal subdivisions induced by π are coherent, - the structure of the fiber polytope does not depend upon the choice of points on the moment curve. We also discuss a new instance with a positive answer to the Generalized Baues Problem, namely that of a projection π:P→Q where Q has only regular subdivisions and P has two more vertices than its dimension.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.