Oriented matroids and complete-graph embeddings on surfaces

We provide a link between topological graph theory and pseudoline arrangements from the theory of oriented matroids. We investigate and generalize a function f that assigns to each simple pseudoline arrangement with an even number of elements a pair of complete-graph embeddings on a surface. Each element of the pair keeps the information of the oriented matroid we started with. We call a simple pseudoline arrangement triangular, when the cells in the cell decomposition of the projective plane are 2-colorable and when one color class of cells consists of triangles only. Precisely for triangular pseudoline arrangements, one element of the image pair of f is a triangular complete-graph embedding on a surface. We obtain all triangular complete-graph embeddings on surfaces this way, when we extend the definition of triangular complete pseudoline arrangements in a natural way to that of triangular curve arrangements on surfaces in which each pair of curves has a point in common where they cross. Thus Ringel's results on the triangular complete-graph embeddings can be interpreted as results on curve arrangements on surfaces. Furthermore, we establish the relationship between 2-colorable curve arrangements and Petrie dual maps. A data structure, called intersection pattern is provided for the study of curve arrangements on surfaces. Finally we show that an orientable surface of genus g admits a complete curve arrangement with at most 2g+1 curves in contrast to the non-orientable surface where the number of curves is not bounded.     

On mixed-integer sets with two integer variables

We show that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with two integer variables is a crooked cross cut (which we defined in 2010). We extend this result to show that crooked cross cuts give the convex hull of mixed-integer sets with more integer variables if the coefficients of the integer variables form a matrix of rank 2. We also present an alternative characterization of the crooked cross cut closure of mixed-integer sets similar to the one on the equivalence of different definitions of split cuts presented in Cook et al. (1990) [4]. This characterization implies that crooked cross cuts dominate the 2-branch split cuts defined by Li and Richard (2008) [8]. Finally, we extend our results to mixed-integer sets that are defined as the set of points (with some components being integral) inside a closed, bounded and convex set.     

Topological imitation of a colored link with the same Dehn surgery manifold

By the topological imitation theory, we construct, from a given colored link, a new colored link with the same Dehn surgery manifold. In particular, we construct a link with a distinguished coloring whose Dehn surgery manifold is a given closed connected oriented 3-manifold except the 3-sphere. As a result, we can naturally generalize the difference between the Gordon–Luecke theorem and the property P conjecture to a difference between a link version of the Gordon–Luecke theorem and the Poincaré conjecture. Similarly, we construct a link with a π₁-distinguished coloring whose Dehn surgery manifold is a given non-simply-connected closed connected oriented 3-manifold. We also construct a link with just two colorings whose Dehn surgery manifolds are the 3-sphere.     

On Scattered Convex Geometries

A convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice Ω(η), that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex sets.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

On degenerate multi-row Gomory cuts

Borozan and Cornuéjols show that valid inequalities for an infinite relaxation for MIPs, relative to some vertex f of the linear relaxation, are determined by maximal lattice-free convex sets containing f. We show that cuts for the original MIP are given by such sets with f in the interior.     

The constrained degree and fixed-point index theory for set-valued maps

In the first part of the paper we give a construction of a topological degree theory for set-valued tangent vector fields with convex and nonconvex values defined on nonsmooth closed subsets of a Banach space. The obtained homotopy invariant is an extension of the classical degree for vector fields on manifolds. In the second part we propose a fixed-point index for inward maps on arbitrary closed convex sets.     

Topological conjugacy of linear endomorphisms of the 2-torus

We describe two complete sets of numerical invariants of topological conjugacy for linear endomorphisms of the two-dimensional torus, i.e., continuous maps from the torus to itself which are covered by linear maps of the plane. The trace and determinant are part of both complete sets, and two candidates are proposed for a third (and last) invariant which, in both cases, can be understood from the topological point of view. One of our invariants is in fact the ideal class of the Latimer-MacDuffee-Taussky theory, reformulated in more elementary terms and interpreted as describing some topology. Merely, one has to look at how closed curves on the torus intersect their image under the endomorphism. Part of the intersection information (the intersection number counted with multiplicity) can be captured by a binary quadratic form associated to the map, so that we can use the classical theories initiated by Lagrange and Gauss. To go beyond the intersection number, and shortcut the classification theory for quadratic forms, we use the rotation number of Poincaré.

     

Existence of Conformal Metrics on Spheres with Prescribed Paneitz Curvature

In this paper we study the problem of prescribing a fourth order conformal invariant (the Paneitz curvature) on the n-sphere, with n 5. Using tools from the theory of critical points at infinity, we provide some topological conditions on the level sets of a given positive function under which we prove the existence of a metric, conformally equivalent to the standard metric, with prescribed Paneitz curvature.Mathematics Subject Classification (2000): 35J60, 53C21, 58J05Send offprint requests to: Khalil El Mehdi     

Moment Sets of Bell–Shaped Distributions: Extreme Points,Extremal Decomposition and Chebysheff Inequalities

The paper deals with sets of distributions which are given by moment conditions and convex constraints on derivatives of their cumulative distribution functions. A general albeit simple method for the study of their extremal structure, extremal decomposition and topological or measure theoretical properties is developed. Its power is demonstrated by the application to bell–shaped distributions. Extreme points of their moment sets are characterized completely (thus filling a gap in the previous theory) and inequalities of Chebysheff type are derived by means of general integral representation theorems.     

The affine representation theorem for abstract convex geometries

A convex geometry is a combinatorial abstract model introduced by Edelman and Jamison which captures a combinatorial essence of “convexity” shared by some objects including finite point sets, partially ordered sets, trees, rooted graphs. In this paper, we introduce a generalized convex shelling, and show that every convex geometry can be represented as a generalized convex shelling. This is “the representation theorem for convex geometries” analogous to “the representation theorem for oriented matroids” by Folkman and Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries, and opens a new research direction in the theory of convex geometries.     

A convex sets in general position

The notion of convex cones in general position has turned out to be useful in convex programming theory. In this paper we extend the notion to convex sets and give some characterizations which yield a better insight into this concept. We also consider the case of convex sets in S-general position.     

Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra

In this paper, we study the relationship between 2D lattice-free cuts, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in ${\mathbb{R}^2}$ , and various types of disjunctions. Recently Li and Richard (2008), studied disjunctive cuts obtained from t-branch split disjunctions of mixed-integer sets (these cuts generalize split cuts). Balas (Presentation at the Spring Meeting of the American Mathematical Society (Western Section), San Francisco, 2009) initiated the study of cuts for the two-row continuous group relaxation obtained from 2-branch split disjunctions. We study these cuts (and call them cross cuts) for the two-row continuous group relaxation, and for general MIPs. We also consider cuts obtained from asymmetric 2-branch disjunctions which we call crooked cross cuts. For the two-row continuous group relaxation, we show that unimodular cross cuts (the coefficients of the two split inequalities form a unimodular matrix) are equivalent to the cuts obtained from maximal lattice-free sets other than type 3 triangles. We also prove that all 2D lattice-free cuts and their S-free extensions are crooked cross cuts. For general mixed integer sets, we show that crooked cross cuts can be generated from a structured three-row relaxation. Finally, we show that for the corner relaxation of an MIP, every crooked cross cut is a 2D lattice-free cut.     

Lifting inequalities: a framework for generating strong cuts for nonlinear programs

In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs. The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the problem.      

Analysis of bounded sets in a topological tensor product

The aim of this paper is to investigate the nature of bounded sets in a topological ∈-tensor product EX_∈* F of any two locally convex topological vector spaces E and F over the same scalar field K. Next, we apply the results of this investigation to the study of each of the following:

1. Totally summable families in EX_∈*F;
2. ∈-tensor product of DF-spaces;
3. Topological nature of the dual of E X_∈*F, where E and F are strong duals of Banach spaces;
4. Properties of bounded sets in an ∈-tensor product of metrizable spaces.

Forπ-tensor product, the result corresponding to (b) is well known (see Grothendieck¹) that if E and F are DF-spaces then EX_π* F and EX_π* F are DF-spaces and that the strong topology on the topological dual (EX_π*F)′, which equals the space of continuous bilinear forms on EXF, coincides with the bibounded topology. We study each of the problems from (a) to (d) for ∈-tensor products. For terminology, notations and the well-known results in the theory of topological vector spaces and the topological tensor products we refer to [1–11]. However, for convenience in presentation of the results of our investigation we give a brief survey of notations and fundamental theorems which are needed throughout this paper.     

Topological convexities, selections and fixed points

A convexity on a set X is a family of subsets of X which contains the whole space and the empty set as well as the singletons and which is closed under arbitrary intersections and updirected unions. A uniform convex space is a uniform topological space endowed with a convexity for which the convex hull operator is uniformly continuous. Uniform convex spaces with homotopically trivial polytopes (convex hulls of finite sets) are absolute extensors for the class of metric spaces; if they are completely metrizable then a continuous selection theorem à la Michael holds. Upper semicontinuous maps have approximate selections and fixed points, under the usual assumptions.     

Abstract ordered compact convex sets and algebras of the (sub)probabilistic powerdomain monad over ordered compact spaces

The majority of categories used in denotational semantics are topological in nature. One of these is the category of stably compact spaces and continuous maps. Previously, Eilenberg–Moore algebras were studied for the extended probabilistic powerdomain monad over the category of ordered compact spaces X and order-preserving continuous maps in the sense of Nachbin. Appropriate algebras were characterized as compact convex subsets of ordered locally convex topological vector spaces. In so doing, functional analytic tools were involved. The main accomplishments of this paper are as follows: the result mentioned is re-proved and is extended to the subprobabilistic case; topological methods are developed which defy an appeal to functional analysis; a more topological approach might be useful for the stably compact case; algebras of the (sub)probabilistic powerdomain monad inherit barycentric operations that satisfy the same equational laws as those in vector spaces. Also, it is shown that it is convenient first to embed these abstract convex sets in abstract cones, which are simpler to work with. Lastly, we state embedding theorems for abstract ordered locally compact cones and compact convex sets in ordered topological vector spaces.     

Generalizing the rattle theorem

The Rattle theorem states that a baby's rattle, the union of a 2-sphere Σ and its interior, is a topological 3-cell if the marble rattler in its interior touches every point of Σ as it rolls around inside the rattle. Other than rattlers that themselves contain marbles (such as a solid ellipsoid), there are no known substitutes for the marble in this theorem. Examples are given to show that some natural rattler choices among convex polyhedra fail to tame the rattle. However Σ is nearly tame in E³ if it can be touched at each of its points by the tip of a cone from a family of congruent cones in Σ∪Int Σ with sufficiently large cone angles.