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.     

Smooth Fano Polytopes with Many Vertices

The \(d\) -dimensional simplicial, terminal, and reflexive polytopes with at least \(3d-2\) vertices are classified. In particular, it turns out that all of them are smooth Fano polytopes. This improves on previous results of Casagrande (Ann Inst Fourier (Grenoble) 56(1):121–130, 2006) and Øbro (Manuscr Math 125(1): 69–79, 2008). Smooth Fano polytopes play a role in algebraic geometry and mathematical physics.     

Roots of Ehrhart Polynomials of Smooth Fano Polytopes

V. Golyshev conjectured that for any smooth polytope P with dim(P)≤5 the roots z∈ℂ of the Ehrhart polynomial for P have real part equal to −1/2. An elementary proof is given, and in each dimension the roots are described explicitly. We also present examples which demonstrate that this result cannot be extended to dimension six.     

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.     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

P-Faithful Partially Ordered Sets

We prove a theorem that describes P-faithful partially ordered sets.     

Splittability for Partially Ordered Sets

A topological space X is said to be splittable over a class P of spaces if for every AX there exists continuous f:XYP such that f(A)f(XA) is empty. A class P of topological spaces is said to be a splittability class if the spaces splittable over P are precisely the members of P. We extend the notion of splittability to partially ordered sets and consider splittability over some elementary posets. We identify precisely which subsets of a poset can be split along over an n-point chain. Using these results it is shown that the union of two splittability classes need not be a splittability class and a necessary condition for P to be a splittability class is given.     

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.     

Regulating Functions on Partially Ordered Sets

We study the so-called Skorokhod reflection problem (SRP) posed for real-valued functions defined on a partially ordered set (poset), when there are two boundaries, considered also to be functions of the poset. The problem is to constrain the function between the boundaries by adding and subtracting nonnegative nondecreasing (NN) functions in the most efficient way. We show existence and uniqueness of its solution by using only order theoretic arguments. The solution is also shown to obey a fixed point equation. When the underlying poset is a σ-algebra of subsets of a set, our results yield a generalization of the classical Jordan–Hahn decomposition of a signed measure. We also study the problem on a poset that has the structure of a tree, where we identify additional structural properties of the solution, and on discrete posets, where we show that the fixed point equation uniquely characterizes the solution. Further interesting posets we consider are the poset of real n-vectors ordered by majorization, and the poset of n × n positive semidefinite real matrices ordered by pointwise ordering of the associated quadratic forms. We say a function on a poset is of bounded variation if it can be written as the difference of two NN functions. The solution to the SRP when the upper and lower boundaries are the identically zero function corresponds to the most efficient or minimal such representation of a function of bounded variation. Minimal representations for several important functions of bounded variation on several of the posets mentioned above are determined in this paper. A version of this paper was presented at the Applied Probability Workshop, in the Mathematisches Forschungsinstitut Oberwolfach, December 2003 (organized by V. Schmidt, A. Hordijk and F. Baccelli); the authors are grateful for the invitation which gave them the opportunity to make substantial progress in finalizing this work in the uniquely wonderful research atmosphere at Oberwolfach. Research supported by DARPA grant N66001-00-C-8062, ONR grant N00014-1-0637 and NSF grant ECS 0123512. This work was supported in part by NSF grant ANI-9903495, the INTAS-00-265 project, and a Carathéodory research award.     

Affine Isomorphism for Partially Ordered Sets

Let A and B be the adjacency matrices of graphs G₁ and G₂ (or the strict zeta matrices of posets P₁ and P₂). Associated with A and B is a particular affine space of matrices, denoted _A,B, such that G₁ is isomorphic to G₂ (resp., P₁ is isomorphic to P₂) if and only if there is a 0-1 matrix in _A,B. Solving this integer programming problem is (notoriously) of unknown complexity, and researchers have considered its relaxation; if there is a nonnegative member of _A,B, then one says that G₁ is fractionally isomorphic to G₂ (resp., P₁ is fractionally isomorphic to P₂.) Several combinatorial characterizations of fractional isomorphism for graphs are known.In this paper we note that fractional isomorphism is not an equivalence relation for posets and introduce a further relaxation by defining P₁ to be affinely isomorphic to P₂ if _A,B is nonempty. (Asking whether _A,B is nonempty is a natural first question preceding the question of whether or not _A,B has a binary member, i.e., whether the graphs or posets are isomorphic.) We prove that affine isomorphism is indeed an equivalence relation on posets and that two posets are affinely ismorphic if and only if the f-vectors of their order complexes are the same. One consequence of this is a proof of an affine version of the Poset Reconstruction Conjecture.     

Toric Rings Arising from Cyclic Polytopes

Let d and n be positive integers with n ≥ d + 1 and 𝒫 ? ? ^d an integral cyclic polytope of dimension d with n vertices, and let K[𝒫] = K[?_≥0𝒜_𝒫] denote its associated semigroup K-algebra, where 𝒜_𝒫 = {(1, α) ∈ ? ^d+1: α ∈ 𝒫} ∩ ? ^d+1 and K is a field. In the present paper, we consider the problem when K[𝒫] is Cohen–Macaulay by discussing Serre's condition (R ₁), and we give a complete characterization when K[𝒫] is Gorenstein. Moreover, we study the normality of the other semigroup K-algebra K[Q] arising from an integral cyclic polytope, where Q is a semigroup generated by its vertices only.     

Tractable Partially Ordered Sets Derived from Root Systems and Biased Graphs

We study new posets Q obtained by removing from a geometric lattice L ofa biased graph certain flats indexed by a simplicial complex . (One example of L is the lattice of flats of thevector matroid of a root system B _n .) We study the structureand compute the characteristic polynomial of Q. With certainchoices of L and , including ones for which Q is alattice interpolating between those of B _n and D _n , we observe curious relationships among the roots of thecharacteristic polynomials of Q, L, and .     

To the Spectral Theory of Partially Ordered Sets

Siberian Mathematical Journal - We suggest an approach to advance the spectral theory of posets. The validity of the Hofmann-Mislove Theorem is established for posets and a characterization is...     

Chen-Fox-Lyndon Factorization for Words over Partially Ordered Sets

The Chen-Fox-Lyndon factorization theorem for words over totally ordered sets is a well-known and important theorem; its applications concern Chen iterated integrals and are used in control and filtering theories. We give a natural generalization for words over partially ordered sets, a question which came up in the context of generation theorems for (generalized) overlapping shuffle algebras. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 14, Algebra, 2004.     

Smooth Fano Polytopes Whose Ehrhart Polynomial Has a Root with Large Real Part

The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this paper, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.     

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.     

Rank Properties of Endomorphisms of Infinite Partially Ordered Sets

The relative rank (S : U) of a subsemigroup U of a semigroupS is the minimum size of a set V S such that U together withV generates the whole of S. As a consequence of a result ofSierpiski, it follows that for U T_X, the monoid of all self-mapsof an infinite set X, rank(T_X : U) is either 0, 1 or 2, or uncountable.In this paper, the relative ranks rank(T_X : O_X) are considered,where X is a countably infinite partially ordered set and O_Xis the endomorphism monoid of X. We show that rank(T_X : O_X) 2 if and only if either: there exists at least one elementin X which is greater than, or less than, an infinite numberof elements of X; or X has |X| connected components. Four examplesare given of posets where the minimum number of members of T_Xthat need to be adjoined to O_X to form a generating set is,respectively, 0, 1, 2 and uncountable. 2000 Mathematics SubjectClassification 08A35 (primary), 06A07, 20M20 (secondary).     

Fixed Point Theorems on Chain Complete Partially Ordered Sets

In this paper, we extend the results of Tarski, Abian and Brown on the completeness of lattices by fixed point theorems, to partially ordered sets or (Po sets) with chain completeness property. We also sharpen some of the existing results on completeness of lattices and fixed-point theorems. We also provide counter examples to some of the claims of R. Taskovic to disprove his theorem.Milan R. Taskovic claims to have proved this theorem but his proof is based on a false argument. In fact most of the contentions of Milan R. Taskovic in [4] are factually incorrect. Actually, reviewer of Taskovics paper has pointed out some of his inaccurate observations. See Mathematical Reviews No. 90b:06007, 06A10.     

Linear Discrepancy and Weak Discrepancy of Partially Ordered Sets

The linear discrepancy of a partially ordered set P=(X,) is the least integer k for which there exists an injection f: XZ satisfying (i) if xy then f(x)<f(y) and (ii) if xy then |f(x)–f(y)|k. This concept is closely related to the weak discrepancy of P studied previously. We prove a number of properties of linear and weak discrepancies and relate them to other poset parameters. Both parameters have applications in ranking the elements of a partially ordered set so that the difference in rank of incomparable elements is minimized.