Algorithms over partially ordered sets

We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.     

Maximal and Minimal Semilattices on Ordered Sets

The map which takes an element of an ordered set to its principal ideal is a natural embedding of that ordered set into its powerset, a semilattice. If attention is restricted to all finite intersections of the principal ideals of the original ordered set, then an embedding into a much smaller semilattice is obtained. In this paper the question is answered of when this construction is, in a certain arrow-theoretic sense, minimal. Specifically, a characterisation is given, in terms of ideals and filters, of those ordered sets which admit a so-called minimal embedding into a semilattice. Similarly, a candidate maximal semilattice on an ordered set can be constructed from the principal filters of its elements. A characterisation of those ordered sets that extend to a maximal semilattice is given. Finally, the notion of a free semilattice on an ordered set is given, and it is shown that the candidate maximal semilattice in the embedding-theoretic sense is the free object.     

Hamiltonian Cycles of Adjacent Triples

A construction is given for ordering triples chosen from an ordered set of elements, so that each triple agrees with each neighbor in two of its members and has third member that is a neighbor of its neighbor's third member. Neighbors here are adjacent in order, and also the first is neighbor to the last among both elements and triples. Joichi and White have given a different construction.     

A constructive approach to examination timetabling based on adaptive decomposition and ordering

In this study, we investigate an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place and hence are listed before the ones in the easy set in the construction process. Moreover, the examinations within each set are ordered using different strategies based on graph colouring heuristics. Initially, the examinations are placed into the easy set. During the construction process, examinations that cannot be scheduled are identified as the ones causing infeasibility and are moved forward in the difficult set to ensure earlier assignment in subsequent attempts. On the other hand, the examinations that can be scheduled remain in the easy set. Within the easy set, a new subset called the boundary set is introduced to accommodate shuffling strategies to change the given ordering of examinations. The proposed approach, which incorporates different ordering and shuffling strategies, is explored on the Carter benchmark problems. The empirical results show that the performance of our algorithm is broadly comparable to existing constructive approaches.     

Problem in combinatorial analysis

A problem on the separation of a finite set in accordance with the properties of its elements is analyzed. A class of sets which are extremal in the sense that their separation by the best criterion is the most asymmetric is introduced. An estimate of the capacity of similar sets is given. The application of the results to the problems of classification and ordering of a finite collection is considered.Translated from Matematicheskie Zametki, Vol. 3, No. 1, pp. 15–20, January, 1968.     

Numerical Procedures in Multiobjective Optimization with Variable Ordering Structures

Multiobjective optimization problems with a variable ordering structure, instead of a partial ordering, have recently gained interest due to several applications. In the previous years, a basic theory has been developed for such problems. The binary relations of a variable ordering structure are defined by a cone-valued map that associates, with each element of the linear space ? ^m , a pointed convex cone of dominated or preferred directions. The difficulty in the study of the variable ordering structures arises from the fact that the binary relations are in general not transitive. In this paper, we propose numerical approaches for solving such optimization problems. For continuous problems a method is presented using scalarization functionals, which allows the determination of an approximation of the infinite optimal solution set. For discrete problems the Jahn–Graef–Younes method, known from multiobjective optimization with a partial ordering, is adapted to allow the determination of all optimal elements with a reduced effort compared to a pairwise comparison.     

Ramsey Numbers for Partially-Ordered Sets

We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.     

Free Triangle Orders

We define a new class of ordered sets, called free triangle orders. These are ordered sets represented by a left-to-right ordering on geometric objects contained in a horizontal strip in the plane. The objects are called 'free triangles', and have one vertex on each of the two boundaries of the strip and one vertex in its interior. These ordered sets generalize the classes of trapezoid and triangle orders studied by Bogart, Möhring, and Ryan, represented by trapezoids and triangles respectively, contained within a strip in the plane, and are a special case of the orders of tube dimension 2 introduced by Habib and co-workers, which are represented by any set of convex bodies contained within a strip in the plane. Our main result is that the class of free triangle orders strictly contains the class of trapezoid orders.     

Minimax problems of discrete optimization invariant under majority operators

A special class of discrete optimization problems that are stated as a minimax modification of the constraint satisfaction problem is studied. The minimax formulation of the problem generalizes the classical problem to realistic situations where the constraints order the elements of the set by the degree of their feasibility, rather than defining a dichotomy between feasible and infeasible subsets. The invariance of this ordering under an operator is defined, and the discrete minimization of functions invariant under majority operators is proved to have polynomial complexity. A particular algorithm for this minimization is described.     

Topological properties of definable sets in ordered Abelian groups of burden 2

We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp-rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle-third set (Theorem 2.9). If it has burden 2 and both an infinite discrete set D and a dense-codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense-codense set are definable.     

Tight Gabor Sets on Discrete Periodic Sets

This paper addresses Gabor analysis on a discrete periodic set. Such a scenario can potentially find its applications in signal processing where signals may present on a union of disconnected discrete index sets. We focus on the Gabor systems generated by characteristic functions. A sufficient and necessary condition for a set to be a tight Gabor set in discrete periodic sets is obtained; discrete periodic sets admitting a tight Gabor set are also characterized; the perturbation of tight Gabor sets is investigated; an algorithm to determine whether a set is a tight Gabor set is presented. Furthermore, we prove that an arbitrary Gabor frame set can be represented as the union of a tight Gabor set and a Gabor Bessel set.     

A flexible model and efficient solution strategies for discrete location problems

Flexible discrete location problems are a generalization of most classical discrete locations problems like p-median or p-center problems. They can be modeled by using so-called ordered median functions. These functions multiply a weight to the cost of fulfilling the demand of a customer, which depends on the position of that cost relative to the costs of fulfilling the demand of other customers.In this paper a covering type of model for the discrete ordered median problem is presented. For the solution of this model two sets of valid inequalities, which reduces the number of binary variables tremendously, and several variable fixing strategies are identified. Based on these concepts a specialized branch & cut procedure is proposed and extensive computational results are reported.     

Discrete Abstractions of Continuous Systems – an Input/Output Point of View

This contribution proposes a hierarchy of discrete ions for a given continuous model. It adopts an input/output point of view, and starts from the continuous system behaviour B _c (i.e., 'the set of all pairs of input and output signals which are compatible with the continuous model equations). The first step is to construct a sequence of behaviours B _l , l =0, 1,..., such that B ₀ ? B ₁ ?... ? B _c. In a second step, nondeterministic Moore automata A_l are generated as minimal realizations for the behaviours B _l . Hence, the continuous base system and its discrete abstractions A l form a totally ordered set of models, where ordering is in the sense of set inclusion of model behaviours or, equivalently, in terms of approximation accuracy. Within this set, there exists a uniquely defined “coarsest” (and therefore least complex) model which allows a given set of specifications to be enforced by discrete feedback. The ordering property implies that this discrete feedback also forces the continuous base system to obey the specifications.     

Implementations of special ordered sets in MP software

Special ordered sets (SOS) have been introduced as a practical device for efficiently handling special classes of nonconvex optimization problems. They are now implemented in most commercial codes for mathematical programming (MP software). The paper gives a survey of possible applications as multiple choice restrictions, conditional multiple choice restrictions, discrete variables, discontinuous variables and piecewise linear functions, global optimization of separable programming problems, alternative right-hand sides, overlapping special ordered sets and the solution of quadratic programming problems. Alternative problem formulations are discussed. Since special ordered sets are not defined uniquely modelling facilities depend on the definition of a special orderedset in a code. The paper demonstrates the superiority of SOS to the application of binary variables if they are treated judiciously.     

Lexicographically ordered trees

We characterize trees whose lexicographic ordering produces an order isomorphic copy of some sets of real numbers, or an order isomorphic copy of some set of ordinal numbers. We characterize trees whose lexicographic ordering is order complete, and we investigate lexicographically ordered ω-splitting trees that, under the open-interval topology of their lexicographic orders, are of the first Baire category. Finally we collect together some folklore results about the relation between Aronszajn trees and Aronszajn lines, and use earlier results of the paper to deduce some topological properties of Aronszajn lines.     

Lexicodes over finite principal ideal rings

Let R be a (possibly noncommutative) finite principal ideal ring. Via a total ordering of the ring elements and an ordered basis a lexicographic ordering of the module \(R^n\) is produced. This is used to set up a greedy algorithm that selects vectors for which all linear combinations with the previously selected vectors satisfy a pre-specified selection property and updates the to-be-constructed code to the linear hull of the vectors selected so far. The output is called a lexicode. This process was discussed earlier in the literature for fields and chain rings. In this paper we investigate the properties of such lexicodes over finite principal ideal rings and show that the total ordering of the ring elements has to respect containment of ideals for the algorithm to produce meaningful results. Only then it is guaranteed that the algorithm is exhaustive and thus produces codes that are maximal with respect to inclusion. It is further illustrated that the output of the algorithm heavily depends on the total ordering and chosen basis.     

Transformational antiatomic characteristic of ordered sets

To any ordered set with a universally maximal element, a semigroup of its transformations with some natural properties that defines the ordered set up to an isomorphism is assigned. The system of such transformation semigroups is proved to be the minimal element in the set of all defining systems of transformation semigroups with respect to the following ordering: one system precedes another if for each ordered set from the class in question, the semigroup of its transformation belonging to the first system is contained in the semigroup of its transformation from the second system. Translated fromMatematicheskie Zametki, Vol. 66, No. 1, pp. 112–119, July, 1999.     

Partially ordered sets and stratification

We employ partially ordered sets to describe the stratification of a social system, using rank to define the strata. We present a simple method of computing the matrix corresponding to the Hasse diagram and prove its correctness. This methodology is applied to analyze the hierarchy of countries that have won at least one Olympic medal. Four different definitions of dominance are given, leading to four different hierarchies and Hasse diagrams. We also prove that any of these definitions preserve any ordering based on giving different weights to gold, silver, and bronze medals. We study dominance between adjacent strata and note how the system changes with time. We present a case analysis for Poland as an illustration of the set of data that can be computed for any country.     

A note on maximal antichains in ordered sets

We examine the question of when two consecutive levels in a product of -chains form an ordered set such that for any antichain, there is a maximal antichain disjoint from it. We characterize the pairs of consecutive levels in the product of t2 -chains that have this property. We also show that there is no upper bound on the heights of ordered sets having this property.The graph of an ordered set is the graph whose points are the elements of the ordered set, and whose edges are the ordered set's 2-element maximal antichains. We construct a class of ordered sets of all widths at least three such that the graph of each ordered set is a path, and we construct an ordered set of infinite width having a connected graph.Research supported by NSERC undergraduate student summer research fellowship, and by NSERC operating grant 69-3378Research supported by ONR contract N00014-85-K-0769     

A theory of recursive dimension for ordered sets

The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172.