Algebras Defined from Ordered Sets and the Varieties they Generate

We investigate ways of representing ordered sets as algebras and how the order relation is reflected in the algebraic properties of the variety (equational class) generated by these algebras. In particular we consider two different but related methods for constructing an algebra with one binary operation from an arbitrary ordered set with a top element. The two varieties generated by all these algebras are shown to be well-behaved in that they are locally finite, finitely based, and have an equationally definable order relation. We exhibit a bijection between the subdirectly irreducible algebras in each variety and the class of all ordered sets with top element. We determine the structure and cardinality of the free algebra on n-free generators and provide sharp bounds on the number of n-generated algebras in each variety. These enumeration results involve the number of quasi-orders on an n-element set.     

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.     

Interval digraphs: An analogue of interval graphs

Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v. Every n-vertex digraph is an intersection digraph of ordered pairs of subsets of an n-set, but not every digraph is an intersection digraph of convex sets in the plane. Interval digraphs are those having representations where all sets are intervals on the real line. Interval digraphs are characterized in terms of the consecutive ones property of certain matrices, in terms of the adjacency matrix and in terms of Ferrers digraphs. In particular, they are intersections of pairs of Ferrers digraphs whose union is a complete digraph.     

Multi-fuzzy sets: An extension of fuzzy sets

In this paper we propose a method to construct more general fuzzy sets using ordinary fuzzy sets as building blocks. We introduce the concept of multi-fuzzy sets in terms of ordered sequences of membership functions. The family of operations T, S, M of multi-fuzzy sets are introduced by coordinate wise t-norms, s-norms and aggregation operations. We define the notion of coordinate wise conjugation of multifuzzy sets, a method for obtaining Atanassov’s intuitionistic fuzzy operations from multi-fuzzy sets. We show that various binary operations in Atanassov’s intuitionistic fuzzy sets are equivalent to some operations in multi-fuzzy sets like M operations, 2-conjugates of the T and S operations. It is concluded that multi-fuzzy set theory is an extension of Zadeh’s fuzzy set theory, Atanassov’s intuitionsitic fuzzy set theory and L-fuzzy set theory.     

Greedy matching in Young's lattice

If the level sets of a ranked partially ordered set are totally ordered, the greedy match between adjacent levels is defined by successively matching each vertex on one level to the first available unmatched vertex, if any, on the next level. Aigner showed that the greedy match produces symmetric chains in the Boolean algebra. We extend that result to partially ordered sets which are products of chains.It is widely thought that for Young's lattices corresponding to rectangles, the greedy match is complete. We show here that the greedy match is, in fact, complete for n×2, n×3 and n×4 rectangles but not for n×k rectangles if k5 and n is sufficiently large.     

Path-Connected Partially Ordered Sets

The graph of a partially ordered set (X, ?) has X as its set of vertices and (x,y) is an edge if and only if x covers y or y covers x. The poset is path-connected if its graph is connected. Two integer-valued metrics, distance and fence, are defined for path-connected posets. Together the values of these metrics determine a path-connected poset to within isomorphism and duality. The result holds for path-connected preordered sets where distance and fence are pseudometrics. The result fails for non-path-connected posets.     

Partition Lattice q-Analogs Related to q-Stirling Numbers

We construct a family of partially ordered sets (posets) that are q-analogs of the set partition lattice. They are different from the q-analogs proposed by Dowling [5]. One of the important features of these posets is that their Whitney numbers of the first and second kind are just the q-Stirling numbers of the first and second kind, respectively. One member of this family [4] can be constructed using an interpretation of Milne [9] for S[n, k] as sequences of lines in a vector space over the Galois field F _q. Another member is constructed so as to mirror the partial order in the subspace lattice.     

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.     

Pairs,sets and sequences in first-order theories

In this paper we study the idea of theories with containers, like sets, pairs, sequences. We provide a modest framework to study such theories. We prove two concrete results. First, we show that first-order theories of finite signature that have functional non-surjective ordered pairing are definitionally equivalent to extensions in the same language of the basic theory of non-surjective ordered pairing. Second, we show that a first-order theory of finite signature is sequential (is a theory of sequences) iff it is definitionally equivalent to an extension in the same language of a system of weak set theory called WS.      

Large antichains in the partition lattice

Consider the partially ordered set of all partitions of an n-element set, ordered by refinement. The sizes of the various ranks within this poset are the Stirling numbers of the second kind. We show that the ratio of the size of the largest antichain to the size of the largest rank exceeds n^1/35 for all n sufficiently large.     

SMOOTHNESS PROPERTIES OF REAL-VALUED FUNCTIONS BASED ON THEIR OSCILLATION

Abstract

We consider the following two selection principles for topological spaces:

Principle 1: For each sequence of dense subsets, there is a sequence of points from the space, the n-th point coming from the n-th dense set, such that this set of points is dense in the space;

Principle 2: For each sequence of dense subsets, there is a sequence of finite sets, the n-th a subset of the n-th dense set, such that the union of these finite sets is dense in the space.

We show that for separable metric space X one of these principles holds for the space C_p (X) of realvalued continuous functions equipped with the pointwise convergence topology if, and only if, a corresponding principle holds for a special family of open covers of X. An example is given to show that these equivalences do not hold in general for Tychonoff spaces. It is further shown that these two principles give characterizations for two popular cardinal numbers, and that these two principles are intimately related to an infinite game that was studied by Berner and Juhász.     

On Pseudocomplemented and Stone Ordered Sets

The aim of this paper is to characterize both the pseudocomplemented and Stone ordered sets in a manner similar to that used previously for Boolean and distributive ordered sets. The sublattice G(A) of the Dedekind–Mac Neille completion DM(A) of an ordered set A generated by A is said to be the characteristic lattice of A. We will show that there are distributive pseudocomplemented ordered sets whose characteristic lattices are not pseudocomplemented. We can define a stronger notion of pseudocomplementedness by demanding that both A and G(A) be pseudocomplemented. It turns out that the two concepts are the same for finite and Stone ordered sets.     

Sphere orders

Ann-sphere order is a finite partially ordered set representable by containment ofn-spheres in Euclidean (n+1)-space. We present a sequence {P _i } of ordered sets such that eachP _i is ann-sphere order only forni; one consequence is that we are able to determine the dimension of a Euclidean space-time manifold from the finite suborders of its causality order.Research supported by ONR grant N00014 85-K-0769.     

Dynkin Diagram Sequences and Stabilization Phenomena

We continue the study of stabilization phenomena for Dynkin diagram sequences initiated in the earlier work of Kleber and the present author. We consider a more general class of sequences than that of this earlier work, and isolate a condition on the weights that gives stabilization of tensor product and branching multiplicities. We show that all the results of the previous article can be naturally generalized to this setting. We also prove some properties of the partially ordered set of dominant weights of indefinite Kac–Moody algebras, and use this to give a more concrete definition of a stable representation ring. Finally, we consider the classical sequences B _n , C _n , D _n that fall outside the purview of the earlier work, and work out some easy-to-describe conditions on the weights which imply stabilization.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

A generalized permutahedron

With respect to a fixedn-element ordered setP, thegeneralized permutahedron Perm(P) is the set of all ordered setsP L, whereL is any permutation of the elements of the underlyingn-element set. Considered as a subset of the extension lattice of ann-element set,Perm(P) is cover-preserving. We apply this to deduce, for instance, that, in any finite ordered setP, there is a comparability whose removal will not increase the dimension, and there is a comparability whose addition toP will not increase its dimension.We establish further properties about the extension lattice which seem to be of independent interest, leading for example, to the characterization of those ordered setsP for which this generalized permutahedron is itself a lattice.Presented by J. Sichler.Dedicated to the memory of Alan DaySupported in part by PRC Mathématiques-Informatique (France) and NSERC (Canada).Supported in part by DFG (Germany) and NSERC (Canada).Supported in part by NSERC (Canada).     

Enumeration of order preserving maps

Three results are obtained concerning the number of order preserving maps of an n-element partially ordered set to itself. We show that any such ordered set has at least 2 ^2n/3 order preserving maps (and 2 ² in the case of length one). Precise asymptotic estimates for the numbers of self-maps of crowns and fences are also obtained. In addition, lower bounds for many other infinite families are found and several precise problems are formulated.Supported by ONR Contract N00014-85-K-0769.Supported by NSF Grant DMS-9011850.Supported by NSERC Grants 69-3378 and 69-0259.     

On some subclasses of well-covered graphs

A set of points in a graph is independent if no two points in the set are adjacent. A graph is well covered if every maximal independent set is a maximum independent set or, equivalently, if every independent set is contained in a maximum independent set. The well-covered graphs are classified by the W_n property: For a positive integer n, a graph G belongs to class W_n if ≥ n and any n disjoint independent sets are contained in n disjoint maximum independent sets. Constructions are presented that show how to build infinite families of W_n graphs containing arbitrarily large independent sets. A characterization of W_n graphs in terms of well-covered subgraphs is given, as well as bounds for the size of a maximum independent set and the minimum and maximum degrees of points in W_n graphs.     

On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give a characterization of extreme points together with an O(n ²) algorithm for discerning whether a given point is an extreme point, wheren is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed posetructure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.     

Maximal dimensional partially ordered sets I. Hiraguchi's theorem

In this paper, I give a new proof of Hiraguchi's Theorem that the dimension of an n-element partially ordered set is at most [frcase|1/2n]. The significant feature of the proof is the lemma which states that a partially ordered set has either a cover of rank 0 or a pair of covers with elements of one incomparable with elements of the other.