Contributions to max-min convex geometry. I: Segments

We give some contributions to the theory of “max-min convex geometry”, that is, convex geometry in the semimodule over the max-min semiring R_max,min=R∪{-∞,+∞}. We introduce “elementary segments” that generalize from n=2 the horizontal, vertical or oblique segments contained in the main bisector of . We show that every segment in is a concatenation of a finite number of elementary subsegments (at most 2n-1, respectively at most 2n-2, in the case of comparable, respectively, incomparable, endpoints x,y). In this first part we study “max-min segments”, and in the subsequent second part (submitted) we study “max-min semispaces” and some of their relations to “max-min convex sets”.     

Asymptotic formulas for the diameter of sections of symmetric convex bodies

Sharpening work of the first two authors, for every proportion λ∈(0,1) we provide exact quantitative relations between global parameters of n-dimensional symmetric convex bodies and the diameter of their random ⌊λn⌋-dimensional sections. Using recent results of Gromov and Vershynin, we obtain an “asymptotic formula” for the diameter of random proportional sections.     

Remarks on some basic concepts in the KKM theory

In the KKM theory, some authors adopt the concepts of the compact closure (ccl), compact interior (cint), transfer compactly closed-valued multimap, transfer compactly l.s.c. multimap, and transfer compactly local intersection property, respectively, instead of the closure, interior, closed-valued multimap, l.s.c. multimap, and possession of a finite open cover property. In this paper, we show that such adoption is inappropriate and artificial. In fact, any theorem with a term with “transfer” attached is equivalent to the corresponding one without “transfer”. Moreover, we can invalidate terms with “compactly” attached by giving a finer topology on the underlying space. In such ways, we obtain simpler formulations of KKM type theorems, Fan-Browder type fixed point theorems, and other results in the KKM theory on abstract convex spaces.     

New affine measures of symmetry for convex bodies

Grünbaum introduced measures of symmetry for convex bodies that measure how far a given convex body is from a centrally symmetric one. Here, we introduce new measures of symmetry that measure how far a given convex body is from one with “enough symmetries”.To define these new measures of symmetry, we use affine covariant points. We give examples of convex bodies whose affine covariant points are “far apart”. In particular, we give an example of a convex body whose centroid and Santaló point are “far apart”.     

Towards Lim

The paper contains an elegant extension of the Nadler fixed point theorem for multivalued contractions (see Theorem 21). It is based on a new idea of the α-step mappings (see Definition 17) being more efficient than α-contractions. In the present paper this theorem is a tool in proving some fixed point theorems for “nonexpansive” mappings in the bead spaces (metric spaces that, roughly speaking, are modelled after convex sets in uniformly convex spaces). More precisely the mappings are nonexpansive on a set with respect to only one point - the centre of this set (see condition (4)). The results are pretty general. At first we assume that the value of the mapping under consideration at this central point looks “sharp” (see Definition 6). This idea leads to a group of theorems (based on Theorem 7). Their proofs are compact and the theorems, in particular, are natural extensions of the classical results for (usual) nonexpansive mappings. In the second part we apply the idea of Lim to investigate the regular sequences and here the proofs are based on our extension of Nadler's Theorem. In consequence we obtain some fixed point theorems that generalise the classical Lim Theorem for multivalued nonexpansive mappings (see e.g. Theorem 26).     

Lifted generalized permutahedra and composition polynomials

Generalized permutahedra are the polytopes obtained from the permutahedron by changing the edge lengths while preserving the edge directions, possibly identifying vertices along the way. We introduce a “lifting” construction for these polytopes, which turns an n  -dimensional generalized permutahedron into an (n+1)$(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff ?s multiplihedron from homotopy theory, and to the more general “nestomultiplihedra”, answering two questions of Devadoss and Forcey.     

A fractional Helly theorem for convex lattice sets

A set of the form , where is convex and denotes the integer lattice, is called a convex lattice set. It is known that the Helly number of d-dimensional convex lattice sets is 2^d. We prove that the fractional Helly number is only d+1: For every d and every α∈(0,1] there exists β>0 such that whenever F₁,…,F_n are convex lattice sets in such that for at least index sets I⊆{1,2,…,n} of size d+1, then there exists a (lattice) point common to at least βn of the F_i. This implies a (p,d+1)-theorem for every p?d+1; that is, if is a finite family of convex lattice sets in such that among every p sets of , some d+1 intersect, then has a transversal of size bounded by a function of d and p.     

On the nontrivial projection problem

The nontrivial projection problem asks whether every finite-dimensional normed space admits a well-bounded projection of nontrivial rank and corank or, equivalently, whether every centrally symmetric convex body (of arbitrary dimension) is approximately affinely equivalent to a direct product of two bodies of nontrivial dimensions. We show that this is true “up to a logarithmic factor.”     

Bead spaces and fixed point theorems

The notion of a bead metric space defined here (see Definition 6) is a nice generalization of that of the uniformly convex normed space. In turn, the idea of a central point for a mapping when combined with the “single central point” property of the bead spaces enables us to obtain strong and elegant extensions of the Browder-Göhde-Kirk fixed point theorem for nonexpansive mappings (see Theorems 14-17). Their proofs are based on a very simple reasoning. We also prove two theorems on continuous selections for metric and Hilbert spaces. They are followed by fixed point theorems of Schauder type. In the final part we obtain a result on nonempty intersection.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

On perimeters of sections of convex polytopes

In his book “Geometric Tomography” Richard Gardner asks the following question. Let P and Q be origin-symmetric convex bodies in R³ whose sections by any plane through the origin have equal perimeters. Is it true that P=Q? We show that the answer is “Yes” in the class of origin-symmetric convex polytopes. The problem is treated in the general case of Rn.     

Projection problems for symmetric polytopes

Let K⊂Rn be a convex body (a compact, convex subset with non-empty interior), ΠK its projection body. Finding the least upper bound, as K ranges over the class of origin-symmetric convex bodies, of the affine-invariant ratio V(ΠK)/V(K)ⁿ⁻¹, being called Schneider's projection problem, is a well-known open problem in the convex geometry. To study this problem, Lutwak, Yang and Zhang recently introduced a new affine invariant functional for convex polytopes in Rn. For origin-symmetric convex polytopes, they posed a conjecture for the new functional U(P). In this paper, we give an affirmative answer to the conjecture in Rn, thereby, obtain a modified version of Schneider's projection problem.     

On structural stability and robustness to bounded rationality

In this paper, we study the model M$M$, a parameterized class of “general games” together with an associated abstract rationality function. We prove that model M$M$ is structurally stable and robust to ?$?$-equilibria for “almost all” parameter values.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Fundamental results for pointfree convex geometry

Inspired by locale theory, we propose “pointfree convex geometry”. We introduce the notion of convexity algebra as a pointfree convexity space. There are two notions of a point for convexity algebra: one is a chain-prime meet-complete filter and the other is a maximal meet-complete filter. In this paper we show the following: (1) the former notion of a point induces a dual equivalence between the category of “spatial” convexity algebras and the category of “sober” convexity spaces as well as a dual adjunction between the category of convexity algebras and the category of convexity spaces; (2) the latter notion of point induces a dual equivalence between the category of “m-spatial” convexity algebras and the category of “m-sober” convexity spaces. We finally argue that the former notion of a point is more useful than the latter one from a category theoretic point of view and that the former notion of a point actually represents a polytope (or generic point) and the latter notion of a point properly represents a point. We also remark on the close relationships between pointfree convex geometry and domain theory.     

A topological colorful Helly theorem

Let be d+1 families of convex sets in . The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if for all choices of then there exists an 1?i?d+1 such that .Our main result is both a topological and a matroidal extension of the colorful Helly theorem. A simplicial complex X is d-Leray if for all induced subcomplexes Y⊂X and i?d.Theorem.LetXbe ad-Leray complex on the vertex setV. Suppose M is a matroidal complex on the same vertex setVwith rank functionρ. IfM⊂Xthen there exists a simplexτ∈Xsuch thatρ(V−τ)?d.     

The geometry of p-convex intersection bodies

Busemann's theorem states that the intersection body of an origin-symmetric convex body is also convex. In this paper we provide a version of Busemann's theorem for p-convex bodies. We show that the intersection body of a p-convex body is q-convex for certain q. Furthermore, we discuss the sharpness of the previous result by constructing an appropriate example. This example is also used to show that IK, the intersection body of K, can be much farther away from the Euclidean ball than K. Finally, we extend these theorems to some general measure spaces with log-concave and s-concave measures.     

Intersections of spherically convex sets

New theorems of Helly type are proved concerning the intersection of convex cones with a common vertex or, equivalently, the intersection of sets on a sphere which are convex in the sense of Robinson. The proofs of these theorems are based on a lemma which is a spherical analog and generalization of Radon's theorem.