Arithmetic of Finite Ordered Sets: Cancellation of Exponents,II

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^PB ^P, then AB. We show that this is true. Further, we introduce an operation C(A ^B), related to Garrett Birkhoff's exponentiation, and determine the structure of the algebra of isomorphism types of finite posets under the operations induced by A+B, A×B, and C(A ^B). Every finite +-indecomposable and ×-indecomposable poset A of more than one element is expressible for unique (up to isomorphism) E and P as AC(E ^P) where P is connected and E is indecomposable for all three operations.     

Interval-Valued Rank in Finite Ordered Sets

We consider the concept of rank as a measure of the vertical levels and positions of elements of partially ordered sets (posets). We are motivated by the need for algorithmic measures on large, real-world hierarchically-structured data objects like the semantic hierarchies of ontological databases. These rarely satisfy the strong property of gradedness, which is required for traditional rank functions to exist. Representing such semantic hierarchies as finite, bounded posets, we recognize the duality of ordered structures to motivate rank functions with respect to verticality both from the bottom and from the top. Our rank functions are thus interval-valued, and always exist, even for non-graded posets, providing order homomorphisms to an interval order on the interval-valued ranks. The concept of rank width arises naturally, allowing us to identify the poset region with point-valued width as its longest graded portion (which we call the “spindle”). A standard interval rank function is naturally motivated both in terms of its extremality and on pragmatic grounds. Its properties are examined, including the relationship to traditional grading and rank functions, and methods to assess comparisons of standard interval-valued ranks.     

Arithmetic of Finite Ordered Sets: Cancellation of Exponents, I

Garrett Birkhoff conjectured in 1942 that when A, B, P are finite posets satisfying A ^P B ^P , then A B. We show that this is true in case P is dismantlable to each of its points, or P is connected and each of A and B is dismantlable to each of its covering pairs.     

Rogers Semilattices of Finite Partially Ordered Sets

It is proved that the principal sublattice of a Rogers semilattice of a finite partially ordered set is definable. For this goal to be met, we present a generalization of the Denisov theorem concerning extensions of embeddings of Lachlan semilattices to ideals of Rogers semilattices.     

Definability in the Substructure Ordering of Simple Graphs

For simple graphs, we investigate and seek to characterize the properties first-order definable by the induced subgraph relation. Let \({\mathcal{P}\mathcal{G}}\) denote the set of finite isomorphism types of simple graphs ordered by the induced subgraph relation. We prove this poset has only one non-identity automorphism co, and for each finite isomorphism type G, the set {G, G ^co } is definable. Furthermore, we show first-order definability in \({\mathcal{P}\mathcal{G}}\) captures, up to isomorphism, full second-order satisfiability among finite simple graphs. These results can be utilized to explore first-order definability in the closely associated lattice of universal classes. We show that for simple graphs, the lattice of universal classes has only one non-trivial automorphism, the set of finitely generated and finitely axiomatizable universal classes are separately definable, and each such universal subclass is definable up to the unique non-trivial automorphism.     

Definability in substructure orderings, IV: Finite lattices

Let ${\mathcal{L}}$ be the ordered set of isomorphism types of finite lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. Our main result is that for every finite lattice L, the set {?, ? ^opp} is definable, where ? and ? ^opp are the isomorphism types of L and its opposite (L turned upside down). We shall show that the only non-identity automorphism of ${\mathcal{L}}$ is the map ${\ell \mapsto \ell^{\rm opp}}$ .     

Definability in substructure orderings, III: Finite distributive lattices

Let ${{\mathcal D}}$ be the ordered set of isomorphism types of finite distributive lattices, where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite distributive lattice D, the set {d, d ^opp} is definable, where d and d ^opp are the isomorphism types of D and its opposite (D turned upside down). We prove that the only non-identity automorphism of ${{\mathcal D}}$ is the opposite map. Then we apply these results to investigate definability in the closely related lattice of universal classes of distributive lattices. We prove that this lattice has only one non-identity automorphism, the opposite map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each element K of the two subsets, {K, K ^opp} is a definable subset of the lattice.     

Smooth Fano Polytopes Arising from Finite Partially Ordered Sets

Gorenstein Fano polytopes arising from finite partially ordered sets will be introduced. Then we study the problem of which partially ordered sets yield smooth Fano polytopes.     

Identities in Ordered Sets

The concept of identities in ordered sets is introduced.     

Necessary Isomorphism Conditions for Rogers Semilattices of Finite Partially Ordered Sets

We establish a condition that is necessary for Rogers semilattices of computable numberings of finite families of computably enumerable sets to be isomorphic.     

On Equivalence Relations in Ordered Sets

A relationship between equivalence relations in finite ordered sets and linear decompositions is presented.     

On Pseudocomplemented and Stone Ordered Sets,Addendum

The notion of pseudocomplementedness is weakened in order to obtain a tractable and consistent property of ordered sets, in particular lattices.     

Functions and Sets of Smooth Substructure: Relationships and Examples

The past decade has seen the introduction of a number of classes of nonsmooth functions possessing smooth substructure, e.g., “amenable functions”, “partly smooth functions”, and “g ° F decomposable functions”. Along with these classes a number of structural properties have been proposed, e.g., “identifiable surfaces”, “fast tracks”, and “primal-dual gradient structures”. In this paper we examine the relationships between these various classes of functions and their smooth substructures. In the convex case we show that the definitions of identifiable surfaces, fast tracks, and partly smooth functions are equivalent. In the nonconvex case we discuss when a primal-dual gradient structure or g ° F decomposition implies the function is partly smooth, and vice versa. We further provide examples to show these classes are not equal.     

Endomorphism Classes of Ordered Sets,Graphs and Lattices

Order - Given a structure S, what other structures S' on the same underlying set satisfy End S $ \subseteq$ End S'? We answer this question for the cases of ordered sets, reflexive...     

Fixed Point Property for Finite Ordered Sets that Contain No Crowns with 6 or More Elements

Order - We prove that, for a finite ordered set P that contains no crowns with 6 or more elements, it can be determined in polynomial time if P has the fixed point property. This result is obtained...     

Definability in substructure orderings, I: finite semilattices

We investigate definability in the set of isomorphism types of finite semilattices ordered by embeddability; we prove, among other things, that every finite semilattice is a definable element in this ordered set. Then we apply these results to investigate definability in the closely related lattice of universal classes of semilattices; we prove that the lattice has no non-identical automorphisms, the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets and each element of the two subsets is a definable element in the lattice.     

Super-Relational Fixed Point Property and Products in Ordered Sets

Super-relational fixed point property for ordered sets is formulated. It is weaker than the strengthened fixed point property and stronger than the product property. Presented at the Summer School on General Algebra and Ordered Sets, Radějov, 3–9 September 2006.     

Monotone Nonincreasing Random Fields on Partially Ordered Sets. II. Probability Distributions on Polyhedral Cones

In this part of the paper, we investigate the structure of an arbitrary measure μ supported by a polyhedral cone C in R ^d in the case where the decumulative distribution function g_μ of the measure μ satisfies certain continuity conditions. If a face Γ of the cone C satisfies appropriate conditions, the restriction μ|_Γint of the measure μ to the interior part of Γ is proved to be absolutely continuous with respect to the Lebesgue measure λ_Γ on the face Γ. Besides, the density of the measure μ|_Γint is expressed as the derivative of the function g_μ multipied by a constant. This result was used in the first part of the paper to find the finite-dimensional distributions of a monotone random field on a poset. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 307, 2004, pp. 5–56.     

Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window

We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We show that under the appropriate scaling, the number of incomparable elements converges to the height of a one dimensional Brownian excursion at a uniformly chosen random time in the interval [0, 1], which follows the Rayleigh distribution.