Convex Pencils of Real Quadratic Forms

We study the topology of the set X of the solutions of a system of two quadratic inequalities in the real projective space ?P ⁿ (e.g. X is the intersection of two real quadrics). We give explicit formulas for its Betti numbers and for those of its double cover in the sphere S ⁿ ; we also give similar formulas for level sets of homogeneous quadratic maps to the plane. We discuss some applications of these results, especially in classical convexity theory. We prove the sharp bound b(X)??2n for the total Betti number of X; we show that for odd n this bound is attained only by a singular?X. In the nondegenerate case we also prove the bound on each specific Betti number b _k (X)??2(k+2).     

Even Set Systems

In phylogenetic combinatorics, the analysis of split systems is a fundamental issue. Here, we observe that there is a canonical one-to-one correspondence between split systems on the one, and “even” set systems on the other hand, i.e., given any finite set X, we show that there is a canonical one-to-one correspondence between the set P (S (X ) ){\mathcal P (\mathcal S (X ) )} consisting of all subsets S{\mathcal S} of the set S (X){\mathcal S (X)} of all splits of the set X (that is, all 2-subsets {A, B}{\{A, B\}} of the power set P (X){\mathcal P (X)} of X for which A ⋃ B = X and A ⋂ B = 0̸ hold) and the set P ^even (P (X)){\mathcal P ^{even} (\mathcal P (X))} consisting of all subsets E of the power set P (X){\mathcal P (X)} of X for which, for each subset Y of X, the number of proper subsets of Y contained in E is even.     

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.     

Approximation of coincidence points and common fixed points of a collection of mappings of metric spaces

On a complete metric space X, we solve the problem of constructing an algorithm (in general, nonunique) of successive approximations from any point in space to a given closed subsetA. We give an estimate of the distance from an arbitrary initial point to the corresponding limit points. We consider three versions of the subset A: (1) A is the complete preimage of a closed subspace H under a mapping from X into the metric space Y; (2) A is the set of coincidence points of n (n > 1) mappings from X into Y; (3) A is the set of common fixed points of n mappings of X into itself (n = 1, 2, …). The problems under consideration are stated conveniently in terms of a multicascade, i.e., of a generalized discrete dynamical system with phase space X, translation semigroup equal to the additive semigroup of nonnegative integers, and the limit set A. In particular, in case (2) for n = 2, we obtain a generalization of Arutyunov’s theorem on the coincidences of two mappings. In case (3) for n = 1, we obtain a generalization of the contraction mapping principle.     

Inequalities and properties of some generalized Orlicz classes and spaces

We discuss and complement the knowledge about generalized Orlicz classes $ \tilde X_\Phi $ and Orlicz spaces X _Φ obtained by replacing the space L ¹ in the classical construction by an arbitrary Banach function space X. Our main aim is to focus on the task to study inequalities in such spaces. We prove a number of new inequalities and also natural generalizations of some classical ones (e.g., Minkowski’s, Hölder’s and Young’s inequalities). Moreover, a number of other basic facts for further study of inequalities and function spaces are included.     

A new characterization of matrices with the consecutive ones property

We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1,…,n} to each of the subsets, does there exist a bijection f:S→{1,…,n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment.     

On Metric Regularity and the Boundary of the Feasible Set in Linear Optimization

This paper deals with semi-infinite linear inequality systems in ? ⁿ and studies the stability of the boundary of their feasible sets. We analyze the equivalence between the metric regularity of the inverse of the boundary set mapping, $\mathcal{N}$ , and the stability of the feasible set mapping in the sense of the maintenance of the consistency. In doing this we provide operational formulae for distances from points to some useful sets. We also include relationships between the regularity moduli corresponding to the mappings $\mathcal{N}$ and the inverse, $\mathcal{M}$ , of the feasible set mapping, and prove their equality for finite systems and some special cases in the semi-infinite framework. Moreover, we provide conditions to assure that the metric regularity of $\mathcal{N}$ is equivalent to the lower semi-continuity of the boundary set mapping, which is important because the latter property has many characterizations. Since the boundary of a feasible set may not be convex, we cannot make use of the general theory for mappings with convex graph, as for example, the Robinson–Ursescu theorem.     

Complexity of Finding Irreducible Components of a Semialgebraic Set

Let W ⊂ Rⁿ be a semialgebraic set defined by a quantifier-free formula with k atomic polynomials of the kind f ∈ Z[X₁, . . . , X_n] such that deg_{X1, . . . , Xn}(f) < d and the absolute values of coefficients of f are less than 2^M for some positive integers d, M. An algorithm is proposed for producing the complexification, Zariski closure, and also for finding all irreducible components of W. The running time of the algorithm is bounded from above by M^O(1)(kd)^nO(1). The procedure is applied to computing a Whitney system for a semialgebraic set and the real radical of a polynomial ideal.     

Sets of nonnegative matrices with positive inhomogeneous products

Let X be a set of k×k matrices in which each element is nonnegative. For a positive integer n, let P(n) be an arbitrary product of n matrices from X, with any ordering and with repetitions permitted. Define X to be a primitive set if there is a positive integer n such that every P(n) is positive [i.e., every element of every P(n) is positive]. For any primitive set X of matrices, define the index g(X) to be the least positive n such that every P(n) is positive. We show that if X is a primitive set, then g(X)?2^k?2. Moreover, there exists a primitive set Y such that g(Y) = 2^k?2.     

Upper Semicontinuity of the Feasible Set Mapping for Linear Inequality Systems

In this paper we characterize the upper semicontinuity of the feasible set mapping at a consistent linear semi-infinite system (LSIS, in brief). In our context, no standard hypothesis is required in relation to the set indexing the constraints and, consequently, the functional dependence between the linear constraints and their associated indices has no special property. We consider, as parameter space, the set of all LSIS having the same index set, endowed with an extended metric to measure the size of the perturbations. We introduce the concept of reinforced system associated with our nominal system. Then, the upper semicontinuity property of the feasible set mapping at the nominal system is characterized looking at the feasible sets of both systems. The fact that this characterization depends only on the nominal system, not involving systems in a neighbourhood, is remarkable. We also provide a necessary and sufficient condition for the aimed property exclusively in terms of the coefficients of the system.     

Dual Characterizations of Set Containments with Strict Convex Inequalities

Characterizations of the containment of a convex set either in an arbitrary convex set or in the complement of a finite union of convex sets (i.e., the set, described by reverse-convex inequalities) are given. These characterizations provide ways of verifying the containments either by comparing their corresponding dual cones or by checking the consistency of suitable associated systems. The convex sets considered in this paper are the solution sets of an arbitrary number of convex inequalities, which can be either weak or strict inequalities. Particular cases of dual characterizations of set containments have played key roles in solving large scale knowledge-based data classification problems where they are used to describe the containments as inequality constraints in optimization problems. The idea of evenly convex set (intersection of open half spaces), which was introduced by W. Fenchel in 1952, is used to derive the dual conditions, characterizing the set containments.     

Colorings of the space ℝn with several forbidden distances

The paper is concerned with the classical problem concerning the chromatic number of a metric space, i.e., the minimal number of colors required to color all points in the space so that the distance (the value of the metric) between points of the same color does not belong to a given set of positive real numbers (the set of forbidden distances). New bounds for the chromatic number are obtained for the case in which the space is ?ⁿ with a metric generated by some norm (in particular, l _p) and the set of forbidden distances either is finite or forms a lacunary sequence.     

Green's relations in finite function semigroups

Let? _n be the set of all partial functions on ann-element setX _n , i.e., the set of all functions whose domain and range are subsets ofX _n . Green's equivalence relations?, ?, ? and? are considered, and the number and cardinality of the corresponding equivalence classes are determined. The number of idempotent and generalized idempotent elements in? _n is also determined.     

On the Continuity of the Optimal Value in Parametric Linear Optimization: Stable Discretization of the Lagrangian Dual of Nonlinear Problems

This paper is focused on the stability of the optimal value, and its immediate repercussion on the stability of the optimal set, for a general parametric family of linear optimization problems in ⁿ. In our approach, the parameter ranges over an arbitrary metric space, and each parameter determines directly a set of coefficient vectors describing the linear system of constraints. Thus, systems associated with different parameters are not required to have the same number (cardinality) of inequalities. In this way, discretization techniques for solving a nominal linear semi-infinite optimization problem may be modeled in terms of suitable parametrized problems. The stability results given in the paper are applied to the stability analysis of the Lagrangian dual associated with a parametric family of nonlinear programming problems. This dual problem is translated into a linear (semi-infinite) programming problem and, then, we prove that the lower semicontinuity of the corresponding feasible set mapping, the continuity of the optimal value function, and the upper semicontinuity of the optimal set mapping are satisfied. Then, the paper shows how these stability properties for the dual problem entail a nice behavior of parametric approximation and discretization strategies (in which an ordinary linear programming problem may be considered in each step). This approximation–discretization process is formalized by means of considering a double parameter: the original one and the finite subset of indices (grid) itself. Finally, the convex case is analyzed, showing that the referred process also allows us to approach the primal problem.Mathematics Subject Classifications (2000) Primary 90C34, 90C31; secondary 90C25, 90C05.     

Hereditary normality of a space of the form ℱ(<Emphasis Type="Italic">X</Emphasis>)

Assuming the continuum hypothesis we construct an example of a nonmetrizable compact set X with the following properties(1) X ⁿ is hereditarily separable for all n ∈ ?(2) X ⁿ \ Δ _n is perfectly normal for every n ∈ ?, where Δ _n is the generalized diagonal of X ⁿ , i.e., the set of points with at least two equal coordinates(3) for every seminormal functor ? that preserves weights and the points of bijectivity the space ? _k (X) is hereditarily normal, where k is the second smallest element of the power spectrum of the functor ?; in particular, X ² and λ ₃ X are hereditarily normal.Our example of a space of this type strengthens the well-known example by Gruenhage of a nonmetrizable compact set whose square is hereditarily normal and hereditarily separable.     

Nonadditive Set Functions on a Finite Set and Linear Inequalities

A set function is a function whose domain is the power set of a set, which is assumed to be finite in this paper. We treat a possibly nonadditive set function, i.e., a set function which does not satisfy necessarily additivity, ?(A) + ?(B) = ?(A ∪ B) forA ∩ B = ∅, as an element of the linear space on the power set. Then some of the famous classes of set functions are polyhedral in that linear space, i.e., expressed by a finite number of linear inequalities. We specify the sets of the coefficients of the linear inequalities for some classes of set functions. Then we consider the following three problems: (a) the domain extension problem for nonadditive set functions, (b) the sandwich problem for nonadditive set functions, and (c) the representation problem of a binary relation by a nonadditive set function, i.e., the problem of nonadditive comparative probabilities.     

Tangent cone and contingent cone to the intersection of two closed sets

For a nonempty closed set C in a real normed vector space X and an inequality solution set, we present several sufficient conditions for the tangent and contingent cones to their intersection to contain the intersections of the corresponding cones. We not only express the contingent cone to a solution set of inequalities and equalities by the directional (or Fréchet) derivatives of the active inequality constraint functions and the Fréchet derivatives of the equality constraint functions but also the tangent cone by the Clarke (or lower Dini, or upper Dini) derivatives of the active inequality constraint functions and the directional derivatives of the equality constraint functions. By using a simple property of the function d_C−d_C^c, we characterize these cones by the hypertangent and hypercontingent vectors to the set C. Furthermore, these results allow us to present new constraint qualifications for the Karush-Kuhn-Tucker conditions.     

Locally bounded coverings and factorial properties of graphs

For a graph property X, let X_n be the number of graphs with vertex set {1,…,n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and n^c₁n≤X_n≤n^c₂n for some constants c₁ and c₂. Hereditary properties with speed slower than factorial are surprisingly well structured. The situation with factorial properties is more complicated and less explored. Only the properties with speeds up to the Bell number are well studied and well behaved. To better understand the behavior of factorial properties with faster speeds we introduce a structural tool called locally bounded coverings and show that a variety of graph properties can be described by means of this tool.     

The size of 3-compatible, weakly compatible split systems

A split system on a finite set X is a set of bipartitions of X. Weakly compatible and k-compatible (k??1) split systems are split systems which satisfy special restrictions on all subsets of a certain fixed size. They arise in various areas of applied mathematics such as phylogenetics and multi-commodity flow theory. In this note, we show that the number of splits in a 3-compatible, weakly compatible split system on a set X of size n is linear in?n.     

Calmness of partially perturbed linear systems with an application to the central path

ABSTRACT

In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Cánovas MJ, López MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375–389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.