Generating and Enumerating Digitally Convex Sets of Trees

A set S of vertices in a graph G with vertex set V is digitally convex if for every vertex \(v \in V\), \(N[v] \subseteq N[S]\) implies \(v \in S\). We show that a vertex belongs to at most half of the digitally convex sets of a graph. Moreover, a vertex belongs to exactly half of the digitally convex sets if and only if it is simplicial. An algorithm that generates all digitally convex sets of a tree is described and sharp upper and lower bounds for the number of digitally convex sets of a tree are obtained. A closed formula for the number of digitally convex sets of a path is derived. It is shown how a binary cotree of a cograph can be used to enumerate its digitally convex sets in linear time.     

Certain Subsets on Which Every Bounded Convex Function Is Continuous

To guarantee every real-valued convex function bounded above on a set is continuous, how ＂thick＂ should the set be？ For a symmetric set A in a Banach space E,the answer of this paper is： Every real-valued convex function bounded above on A is continuous on E if and only if the following two conditions hold： i） spanA has finite co-dimentions and ii） coA has nonempty relative interior. This paper also shows that a subset A C E satisfying every real-valued convex function bounded above on A is continuous on E if （and only if） every real-valued linear functional bounded above on A is continuous on E, which is also equivalent to that every real-valued convex function bounded on A is continuous on E.     

Extremal Unital Completely Positive Maps and Their Symmetries

We consider the set \(P_1({\mathcal A},{\mathcal M})\) (respectively \(CP_1({\mathcal A},{\mathcal M})\) of unital positive (completely) maps from a \(C^*\) algebra \({\mathcal A}\) to a von-Neumann sub-algebra \({\mathcal M}\) of \({\mathcal B}({\mathcal H})\), the algebra of bounded linear operators on a Hilbert space \({\mathcal H}\). We study the extreme points of the convex set \(P_1({\mathcal A},{\mathcal M})\) (\(CP_1({\mathcal A},{\mathcal M})\)) via their canonical lifting to the convex set of (unital) positive (completely) normal maps from \(\hat{{\mathcal A}}\) to \({\mathcal M}\), where \({\mathcal A}^{**}\) is the universal enveloping von-Neumann algebra over \({\mathcal A}\). If \({\mathcal A}={\mathcal M}\) then a (completely) positive map \(\tau \) admits a unique decomposition into a sum of a normal and a singular (completely) positive maps. Furthermore, if \({\mathcal M}\) is a factor then a unital complete positive map is a unique convex combination of unital normal and singular completely positive maps. We also used a duality argument to find a criteria for an element in the convex set of unital completely positive maps with a given faithful normal invariant state on \({\mathcal M}\) to be extremal. In our investigation, gauge symmetry in the minimal Stinespring representation of a completely positive map and Kadison theorem on order isomorphism played an important role.     

LR Characterization of Chirotopes of Finite Planar Families of Pairwise Disjoint Convex bodies

We extend the classical LR characterization of chirotopes of finite planar families of points to chirotopes of finite planar families of pairwise disjoint convex bodies: a map $\chi $ χ on the set of 3-subsets of a finite set $I$ I is a chirotope of finite planar families of pairwise disjoint convex bodies if and only if for every 3-, 4-, and 5-subset $J$ J of $I$ I the restriction of $\chi $ χ to the set of 3-subsets of $J$ J is a chirotope of finite planar families of pairwise disjoint convex bodies. Our main tool is the polarity map, i.e., the map that assigns to a convex body the set of lines missing its interior, from which we derive the key notion of arrangements of double pseudolines, introduced for the first time in this paper.     

On convexity of hypersurfaces in the hyperbolic space

In the Hyperbolic space \({\mathbb{H}^n}\) (n ≥ 3) there are uncountably many topological types of convex hypersurfaces. When is a locally convex hypersurface in \({\mathbb{H}^n}\) globally convex, that is, when does it bound a convex set? We prove that any locally convex proper embedding of an (n ? 1)-dimensional connected manifold is the boundary of a convex set whenever the complement of (n ? 1)-flats of the resulting hypersurface is connected.     

Concave functions,blaschke products,and polygonal mappings

We consider the class Co(p) of all conformal maps of the unit disk onto the exterior of a bounded convex set. We prove that the triangle mappings, i.e., the functions that map the unit disk onto the exterior of a triangle, are among the extreme points of the closed convex hull of Co(p). Moreover, we prove a conjecture on the closed convex hull of Co(p) for all p ∈ (0, 1) which had partially been proved by the authors for some values of p ∈ (0, 1).     

Convex equipartitions: the spicy chicken theorem

We show that, for any prime power $n$ and any convex body $K$ (i.e., a compact convex set with interior) in $\mathbb{R }^d$ , there exists a partition of $K$ into $n$ convex sets with equal volumes and equal surface areas. Similar results regarding equipartitions with respect to continuous functionals and absolutely continuous measures on convex bodies are also proven. These include a generalization of the ham-sandwich theorem to arbitrary number of convex pieces confirming a conjecture of Kaneko and Kano, a similar generalization of perfect partitions of a cake and its icing, and a generalization of the Gromov–Borsuk–Ulam theorem for convex sets in the model spaces of constant curvature.     

On the Stability of the Motzkin Representation of Closed Convex Sets

A set is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set with a closed convex cone. This paper analyzes the continuity properties of the set-valued mapping associating to each couple $\left( C,D\right) $ formed by a compact convex set C and a closed convex cone D its Minkowski sum C?+?D. The continuity properties of other related mappings are also analyzed.     

Invariant convex sets in polar representations

We study a compact invariant convex set E in a polar representation of a compact Lie group. Polar representations are given by the adjoint action of K on p, where K is a maximal compact subgroup of a real semisimple Lie group G with Lie algebra g = k ⊕ p. If a ? p is a maximal abelian subalgebra, then P = E ∩ a is a convex set in a. We prove that up to conjugacy the face structure of E is completely determined by that of P and that a face of E is exposed if and only if the corresponding face of P is exposed. We apply these results to the convex hull of the image of a restricted1 momentum map.     

On representations of the feasible set in convex optimization

We consider the convex optimization problem \({\min_{\mathbf{x}} \{f(\mathbf{x}): g_j(\mathbf{x})\leq 0, j=1,\ldots,m\}}\) where f is convex, the feasible set \({\mathbf{K}}\) is convex and Slater’s condition holds, but the functions g _j ’s are not necessarily convex. We show that for any representation of \({\mathbf{K}}\) that satisfies a mild nondegeneracy assumption, every minimizer is a Karush-Kuhn-Tucker (KKT) point and conversely every KKT point is a minimizer. That is, the KKT optimality conditions are necessary and sufficient as in convex programming where one assumes that the g _j ’s are convex. So in convex optimization, and as far as one is concerned with KKT points, what really matters is the geometry of \({\mathbf{K}}\) and not so much its representation.     

Convex hull of Brownian motion ind-dimensions

We supposeK(w) to be the boundary of the closed convex hull of a sample path ofZ _t(w), 0 ≦t ≦ 1 of Brownian motion ind-dimensions. A combinatorial result of Baxter and Borndorff Neilson on the convex hull of a random walk, and a limiting process utilizing results of P. Levy on the continuity properties ofZ _t(w) are used to show that the curvature ofK(w) is concentrated on a metrically small set.     

Planar Point Sets With Large Minimum Convex Decompositions

We show the existence of sets with $n$ points ( $n\ge 4$ ) for which every convex decomposition contains more than $\frac{35}{32}n-\frac{3}{2}$ polygons, which refutes the conjecture that for every set of $n$ points there is a convex decomposition with at most $n+C$ polygons. For sets having exactly three extreme points we show that more than $n+\sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition.     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

Finite Sets as Complements of Finite Unions of Convex Sets

Suppose S?? ^d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ? ^d ?S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ? _S . We consider the graph \(\mathcal {G}_{S}\) whose edges are the 2-element edges of ? _S , and we show that, when d=2, for any sufficiently large set S, the chromatic number of \(\mathcal{G}_{S}\) will be large, even though there exist arbitrarily large finite sets S for which \(\mathcal{G}_{S}\) does not contain large cliques.     

Combinatorial geometry of belt bodies

In this paper we consider a new class of convex bodies which was introduced in [11]. This is the class of belt bodies, and it is a natural generalization of the class of zonoids (see the surveys [18, 28, 24]). While the class of zonoids is not dense in the family of all centrally symmetric, convex bodies, the class of belt bodies is dense in the set of all convex bodies. Nevertheless, we shall extend solutions of combinatorial problems for zonoids (cf. [2, 12]) to the class of belt bodies. Therefore, we first introduce the set of belt bodies by using zonoids as starting point. (To make the paper self-contained, a few parts of the approach from [11] are given repeatedly.) Second, complete solutions of three well-known (and generally unsolved) problems from the combinatorial geometry of convex bodies are given for the class of belt bodies. The first of these, connected with the names of I. Gohberg and H. Hadwiger, is the problem of covering a convex body with smaller homothetic copies, or the equivalent illumination problem. The second is the Szökefalvi-Nagy problem, which asks for the determination of the convex bodies whose families of translates have a given Helly dimension. The third problem concerns special fixing systems, a notion which is due to L. Fejes Tóth. These solutions consist of improved and more general approaches to recently solved problems (as in the case of the Helly-dimensional classification of belt bodies) or new results (as those concerning minimal fixing systems, providing also an answer to a problem of B. Grünbaum which is not only restricted to belt bodies).     

An analogue of a theorem of van der Waerden,and its application to two-distance preserving mappings

A theorem of van der Waerden reads that an equilateral pentagon in Euclidean 3-space \({\mathbb {E}}^3\) with all diagonals of the same length is necessarily planar and its vertex set coincides with the vertex set of some convex regular pentagon. We prove the following many-dimensional analogue of this theorem: for \(n\geqslant 2,\) every n-dimensional cross-polytope in \({\mathbb {E}}^{2n-2}\) with all diagonals of the same length and all edges of the same length necessarily lies in \({\mathbb {E}}^n\) and hence is a convex regular cross-polytope. We also apply our theorem to the study of two-distance preserving mappings of Euclidean spaces.     

Ball and spindle convexity with respect to a convex body

Let ${C \subset \mathbb{R}^n}$ be a convex body. We introduce two notions of convexity associated to C. A set K is C-ball convex if it is the intersection of translates of C, or it is either ${\emptyset}$ , or ${\mathbb{R}^n}$ . The C-ball convex hull of two points is called a C-spindle. K is C-spindle convex if it contains the C-spindle of any pair of its points. We investigate how some fundamental properties of conventional convex sets can be adapted to C-spindle convex and C-ball convex sets. We study separation properties and Carathéodory numbers of these two convexity structures. We investigate the basic properties of arc-distance, a quantity defined by a centrally symmetric planar disc C, which is the length of an arc of a translate of C, measured in the C-norm that connects two points. Then we characterize those n-dimensional convex bodies C for which every C-ball convex set is the C-ball convex hull of finitely many points. Finally, we obtain a stability result concerning covering numbers of some C-ball convex sets, and diametrically maximal sets in n-dimensional Minkowski spaces.     

A structural characterization of numéraires of convex sets of nonnegative random variables

We introduce the concept of numéraire s of convex sets in ${L^0_{+}}$ , the nonnegative orthant of the topological vector space L ⁰ of all random variables built over a probability space. A necessary and sufficient condition for an element of a convex set ${\mathcal{C} \subseteq L^0_{+}}$ to be a numéraire of ${\mathcal{C}}$ is given, inspired from ideas in financial mathematics.     

On convex iterative roots of non-monotonic mappings

Let I be an interval. We consider the non-monotonic convex self-mappings \(f:I\rightarrow I\) such that \(f^2\) is convex. They have the property that all iterates \(f^n\) are convex. In the class of these mappings we study three families of functions possessing convex iterative roots. A function f is said to be iteratively convex if f possesses convex iterative roots of all orders. A mapping f is said to be dyadically convex if for every \(n\ge 2\) there exists a convex iterative root \(f^{1/2^n}\) of order \(2^n\) and the sequence \(\{f^{1/2^n}\}\) satisfies the condition of compatibility, that is \( f^{1/2^n}\circ f^{1/2^n}= f^{1/2^{n-1}}.\) A function f is said to be flowly convex if it possesses a convex semi-flow of f, that is a family of convex functions \(\{f^t,t>0\}\) such that \(f^t\circ f^s=f^{t+s}, \ \ t,s >0\) and \(f^1=f\). We show the relations among these three types of convexity and we determine all convex iterative roots of non-monotonic functions.