Complementation in the Lattice of Locally Convex Topologies

We find all locally convex homogeneous topologies on (?, ≤?) and determine which of these have locally convex complements. Among the locally convex topologies on an n-point totally ordered set, each has a locally convex complement and, for n?≥?3, at least n???2 of them have 2 ^n???1 locally convex complements. For any infinite cardinal κ, totally ordered spaces of cardinality κ which have exactly 1, exactly κ, and exactly 2 ^κ locally convex complements are exhibited.     

Extreme points for convex mappings ofB n

We exhibit a collection of extreme points of the family of normalized convex mappings of the open unit ball of ℂ ⁿ forn≥2. These extreme points are defined in terms of the extreme points of a closed ball in the Banach space of homogeneous polynomials of degree 2 in ℂ ⁿ⁻¹, which are fully classified. Two examples are given to show that there are more convex mappings than those contained in the closed convex hull of the set of extreme points here exhibited.     

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.

     

An interior proximal method in vector optimization

This paper studies the vector optimization problem of finding weakly efficient points for maps from Rⁿ to R^m, with respect to the partial order induced by a closed, convex, and pointed cone C⊂R^m, with nonempty interior. We develop for this problem an extension of the proximal point method for scalar-valued convex optimization problem with a modified convergence sensing condition that allows us to construct an interior proximal method for solving VOP on nonpolyhedral set.     

The space clcv(? n ) with the Hausdorff-Bebutov metric and statistically invariant sets of control systems

We obtain conditions that allow one to evaluate the relative frequency of occurrence of the reachable set of a control system in a given set. If the relative frequency of occurrence in this set is 1, then the set is said to be statistically invariant. It is assumed that the images of the right-hand side of the differential inclusion corresponding to the given control system are convex, closed, but not necessarily compact. We also study the basic properties of the space clcv(? ⁿ ) of nonempty closed convex subsets of ? ⁿ with the Hausdorff-Bebutov metric.     

Generating sets for lattices of dimension two

The dimension of a partially ordered set P is the smallest integer n (if it exists) such that the partial order on P is the intersection of n linear orders. It is shown that if L is a lattice of dimension two containing a sublattice isomorphic to the modular lattice M_2n+1, then every generating set of L has at least n+2 elements. A consequence is that every finitely generated lattice of dimension two and with no infinite chains is finite.     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

Secant varieties of toric varieties

Let X_P be a smooth projective toric variety of dimension n embedded in P^r using all of the lattice points of the polytope P. We compute the dimension and degree of the secant variety . We also give explicit formulas in dimensions 2 and 3 and obtain partial results for the projective varieties X_A embedded using a set of lattice points A⊂P∩Zⁿ containing the vertices of P and their nearest neighbors.     

Contact points of convex bodies

LetB be a convex body in ? ⁿ and let ? be an ellipsoid of minimal volume containingB. By contact points ofB we mean the points of the intersection between the boundaries ofB and ?. By a result of P. Gruber, a generic convex body in ? ⁿ has (n+3)·n/2 contact points. We prove that for every ?>0 and for every convex bodyB ? ? ⁿ there exists a convex bodyK having $$m \leqslant C(\varepsilon ) \cdot n\log ^3 n$$ contact points whose Banach-Mazur distance toB is less than 1+?. We prove also that for everyt>1 there exists a convex symmetric body Γ ? ? ⁿ so that every convex bodyD ? ? ⁿ whose Banach-Mazur distance to Γ is less thant has at least (1+c ₀/t ²)·n contact points for some absolute constantc ₀. We apply these results to obtain new factorizations of Dvoretzky-Rogers type and to estimate the size of almost orthogonal submatrices of an orthogonal matrix.     

A polyominoes-permutations injection and tree-like convex polyominoes

Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z², considered identical if their cell sets are equal up to an integral translation. We introduce a novel injection from the set of polyominoes with n cells to the set of permutations of [n], and classify the families of convex polyominoes and tree-like convex polyominoes as classes of permutations that avoid some sets of forbidden patterns. By analyzing the structure of the respective permutations of the family of tree-like convex polyominoes, we are able to find the generating function of the sequence that enumerates this family, conclude that this sequence satisfies the linear recurrence an=6an−1−14an−2+16an−3−9an−4+2an−5, and compute the closed-form formula an=²n+2−(n³−n²+10n+4)/2.     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

Coloring copoints of a planar point set

To a set of n points in the plane, one can associate a graph that has less than n² vertices and has the property that k-cliques in the graph correspond vertex sets of convex k-gons in the point set. We prove an upper bound of 2^k-1 on the size of a planar point set for which the graph has chromatic number k, matching the bound conjectured by Szekeres for the clique number. Constructions of Erd?s and Szekeres are shown to yield graphs that have very low chromatic number. The constructions are carried out in the context of pseudoline arrangements.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

Multidimensional Farey partitions

The linear action of SL(n, ?₊) induces lattice partitions on the (n − 1)-dimensional simplex †n−1. The notion of Farey partition raises naturally from a matricial interpretation of the arithmetical Farey sequence of order r. Such sequence is unique and, consequently, the Farey partition of order r on A 1 is unique. In higher dimension no generalized Farey partition is unique. Nevertheless in dimension 3 the number of triangles in the various generalized Farey partitions is always the same which fails to be true in dimension n > 3. Concerning Diophantine approximations, it turns out that the vertices of an n-dimensional Farey partition of order r are the radial projections of the lattice points in ?₊ⁿ ∩ [0, r]ⁿ whose coordinates are relatively prime. Moreover, we obtain sequences of multidimensional Farey partitions which converge pointwisely.     

Generalizations of a combinatorial lemma of Kelly

Two sets in R^m are said to be n-separated if, for every n distinct points p₁,…, p_n of one set, there is a point of the other in the relative interior of the convex cover of {p₁,…, p_n. We obtain some results concerning the dimension of the flat spanned by the union of n-separated sets and pose several further questions.     

General decomposition theorems form-convex sets in the plane

A setS inR ^dis said to bem-convex,m≧2, if and only if for everym distinct points inS, at least one of the line segments determined by these points lies inS. Clearly any union ofm?1 convex sets ism-convex, yet the converse is false and has inspired some interesting mathematical questions: Under what conditions will anm-convex set be decomposable intom?1 convex sets? And for everym≧2, does there exist aσ(m) such that everym-convex set is a union ofσ(m) convex sets? Pathological examples convince the reader to restrict his attention to closed sets of dimension≦3, and this paper provides answers to the questions above for closed subsets of the plane. IfS is a closedm-convex set in the plane,m ≧ 2, the first question may be answered in one way by the following result: If there is some lineH supportingS at a pointp in the kernel ofS, thenS is a union ofm ? 1 convex sets. Using this result, it is possible to prove several decomposition theorems forS under varying conditions. Finally, an answer to the second question is given: Ifm≧3, thenS is a union of (m?1)³2 ^m?3 or fewer convex sets.     

The Hemivariational Inequalities for an Upper Semicontinuous Set-valued Mapping

We establish some existence results for hemivariational inequalities of Stampacchia type involving an upper semicontinuous set-valued mapping on a bounded, closed and convex subset in ? ⁿ . We also derive a sufficient condition for the existence and boundedness of solution, without assuming boundedness of the constraint set.     

Cohomology of incidence coalgebras

The cohomology groups Hⁿ(M, C) are studied, where C is the incidence coalgebra of a locally finite partially ordered set P and where M is a C-C comodule depending on a convex coarsening of the given partial order on P. The case where P is a geometric lattice and the convex coarsening is just the equality relation is emphasized.     

Erd?s–Szekeres Theorem for Point Sets with Forbidden Subconfigurations

According to the Erd?s?CSzekeres theorem, every set of n points in the plane contains roughly logn points in convex position. We investigate how this bound changes if our point set does not contain a subset that belongs to a fixed order type.     

The complex of non-crossing diagonals of a polygon

Given a convex n-gon P in R² with vertices in general position, it is well known that the simplicial complex θ(P) with vertex set given by diagonals in P and facets given by triangulations of P is the boundary complex of a polytope of dimension n−3. We prove that for any non-convex polygonal region P with n vertices and h+1 boundary components, θ(P) is a ball of dimension n+3h−4. We also provide a new proof that θ(P) is a sphere when P is convex with vertices in general position.