Narrow Results

The Poset Cover Problem is the problem where the input is a set of linear orders and the goal is to find a minimum set of posets that generates exactly all the given linear orders. The computational complexity of the decision version of the problem is already known; it is NP-Complete. However, the approximation complexity or approximability of the problem is not yet known.

In this paper, we show the approximability of two simple variations of the problem where the poset being considered are Hammock posets having hammocks of size 2. The first is Hammock(2, 2, 2)-Poset Cover Problem where the solution is a set of Hammock posets with 3 hammocks of size 2. This problem has been shown to be NP-Complete and in this paper we show that it is 2.7-approximable. The second variation which is more general than the first one considers Hammock posets with any number of hammocks of size 2 and we show that it is $H(n)-\frac{196}{300}-\text{approximable}$.

In this paper, we investigate the root distribution of the Ehrhart polynomials of lattice polytopes. When the lattice polytope is reflexive, the roots of the Ehrhart polynomial distribute symmetrically with respect to the line $\mathrm{\text{Re}}(z)=-\frac{1}{2}$. A special case of this distribution is when all the roots lie on this line. Our main concern is to find out which reflexive polytopes satisfy this special condition. Such lattice polytopes are called CL-polytopes. Another special case opposite to this is when all the roots are real. Such lattice polytopes are called real polytopes. The first topic of this paper is the Ehrhart polynomials of equatorial spheres, which are related to graded posets. We discuss the CL-ness of the equatorial Ehrhart polynomials for complete graded posets and zig-zag posets. The second topic is to investigate the relation of the root distribution of the Ehrhart polynomials of a reflexive polytope $Q$ and its dual $Q^{\vee }$. We discuss the CL-ness and realness of $Q$ and $Q^{\vee }$ in pair, of dimensions up to 4. Throughout this paper, we investigate these problems by computer calculation.

Let $(P,\le )$ be an atomic poset with the least element $0$. The complement of the intersection graph of ideals of $P$, denoted by $\mathrm{\Gamma }(P)$, is defined to be a graph whose vertices are all non-trivial ideals of $P$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I\cap J=\{0\}$. In this paper, we consider the complement of the intersection graph of ideals of a poset. We prove that $\mathrm{\Gamma }(P)$ is totally disconnected or $\text{diam}(\mathrm{\Gamma }(P)\backslash 𝔄)\in \{1,2,3\}$, where $𝔄$ is the set of all isolated vertices of $\mathrm{\Gamma }(P)$. We show that $gr(\mathrm{\Gamma }(P))\in \{3,4,\infty \}$. Also, we characterize all posets whose complement of the intersection graph is forest, unicyclic or complete $r$-partite graph. Among other results, we prove that $\mathrm{\Gamma }(P)$ is weakly perfect; and it is perfect if and only if $|\text{Atom}(P)|\le 4$. Finally, we show that $\mathrm{\Gamma }(P)$ is class $1$, where $P=\text{Atom}(P)\cup \{0\}$.

This article is devoted to the study of several algebras related to symmetric functions, which admit linear bases labelled by various combinatorial objects: permutations (free quasi-symmetric functions), standard Young tableaux (free symmetric functions) and packed integer matrices (matrix quasi-symmetric functions). Free quasi-symmetric functions provide a kind of noncommutative Frobenius characteristic for a certain category of modules over the 0-Hecke algebras. New examples of indecomposable H_n(0)-modules are discussed, and the homological properties of H_n(0) are computed for small n. Finally, the algebra of matrix quasi-symmetric functions is interpreted as a convolution algebra.

Among the unsolved problems of enumeration of graphs, one of the most difficult is the problem of enumeration of transitive digraphs, which is equivalent to the problem of enumeration of finite partial orders and is equivalent to the problem of enumeration of finite labeled $T_0$-topologies. The sequence $\{T_0(n)\}$, where $T_0(n)$ is the number of all labeled $T_0$-topologies defined on an n-set, has been studied from different points of view. In the previous work of the second author, a formula was obtained in which the number $T_0(n)$ is represented as a linear combination of numbers $W(\overline{p})$ (where the sequences $\overline{p}=(p_1,\dots ,p_k)\vDash n$ are compositions of the number n). Recurrent relations between individual numbers $W(\cdot )$ were obtained. In this paper, new recursive formulas between separate numbers $W(\cdot )$ are obtained.

For a class of algebras, denote by Con_c the class of all (∨, 0)-semilattices isomorphic to the semilattice Con_cA of all compact congruences of A, for some A in . For classes and of algebras, we denote by the smallest cardinality of a (∨, 0)-semilattices in Con_c which is not in Con_c if it exists, ∞ otherwise. We prove a general theorem, with categorical flavor, that implies that for all finitely generated congruence-distributive varieties and , is either finite, or ℵ_n for some natural number n, or ∞. We also find two finitely generated modular lattice varieties and such that , thus answering a question by J. Tůma and F. Wehrung.

A bounded poset $P:=(P,0,1,\le )$ is said to be lower finite if $P$ is infinite and for all $1\ne x\in P$, there are but finitely many $y\in P$ such that $y\le x.$ In this paper, we classify the modules $M$ over a commutative ring $R$ with identity with the property that the lattice $L_R(M)$ of $R$-submodules $M$ (under set-theoretic containment) is lower finite. Our results are summarized in Theorem 3.1 at the end of this note.

In this paper, we have proved that minimum condition in a pseudo-ordered set (psoset) is equivalent to the descending pseudo-chain condition. Characterization of a pseudo-chain in an acyclic psoset is obtained using graph theoretic approach as transitivity need not hold in psosets. Skala proved that every complete trellis has Fixed Point Property. A counterexample given in this paper shows that trellis having Fixed Point Property need not be complete. The notion of weakly isotone mapping and Strong Fixed Point Property is introduced in a psoset and the characterization of weakly isotone mapping is obtained. It is proved that a connected psoset containing a nontrivial cycle does not have Strong Fixed Point Property.

Categorification of some integer sequences are obtained by enumerating the number of sections in the Auslander–Reiten quiver of algebras of finite representation type.

A finite poset (P ≼ S) determines a finite dimensional algebra T_P over the field 𝔽 of two elements, with an upper triangular representation. We determine the structure of the radical of the representation algebra A of the monoid (T_P,·) over a field of characteristic different from 2. We also consider degenerations of A over a complete discrete valuation ring with residue field of characteristic 2.

We continue studying net bundles over partially ordered sets (posets), defined as the analogues of ordinary fiber bundles. To this end, we analyze the connection between homotopy, net homology and net cohomology of a poset, giving versions of classical Hurewicz theorems. Focusing our attention on Hilbert net bundles, we define the K-theory of a poset and introduce functions over the homotopy groupoid satisfying the same formal properties as Chern classes. As when the given poset is a base for the topology of a space, our results apply to the category of locally constant bundles.

The elements of a finite partial order P can be identified with the maximal indecomposable two-sided ideals of its incidence algebra , and then for two such ideals, I ≺ J ⇔ IJ ≠ 0. This offers one way to recover a poset from its incidence algebra. In the course of proving the above, we classify all of the two-sided ideals of .

It is known that a poset can be embedded into a distributive lattice if, and only if, it satisfies the prime filter separation property. We describe here a class of “prime filter completions” for posets with the prime filter separation property that are completely distributive lattices generated by the poset and preserve existing finite meets and joins. The free completely distributive lattice generated by a poset can be obtained through such a prime filter completion. We also show that every completely distributive completion of a poset with the prime filter separation property is representable as a canonical extension of the poset with respect to some set of filters and ideals. The connections between the prime filter completions and canonical extensions are described and yield the following corollary: the canonical extension of any distributive lattice is the free completely distributive lattice generated by the lattice. A construction that is a variant of the prime filter completion is given that can be used to obtain the free distributive lattice generated by a poset. In addition, it is shown that every distributive lattice extension of the poset can be represented by such a construction. Finally, we show that a poset with the prime filter separation property and the free distributive lattice generated by it generates the same free completely distributive lattice.

In this paper, we characterize complete partite zero-divisor graphs of posets via the ideals of the posets. In particular, for complete bipartite zero-divisor graphs, we give a characterization based on the prime ideals of the posets.

We introduce a generic identity based on the Ahlswede–Zhang (AZ) function, which can be considered as a template to establish AZ-style identities. Many AZ-style identities can be derived from the generic identity.

For a partially ordered set P, let Co(P) denote the lattice of all order-convex subsets of P. For a positive integer n, we denote by (resp., SUB(n)) the class of all lattices that can be embedded into a lattice of the form

(1) Both classes and SUB(n), for any positive integer n, are locally finite, finitely based varieties of lattices, and we find finite equational bases of these varieties.

(2) The variety is the quasivariety join of all the varieties SUB(n), for 1≤n<ω, and it has only countably many subvarieties. We classify these varieties, together with all the finite subdirectly irreducible members of .

(3) Every finite subdirectly irreducible member of is projective within , and every subquasivariety of is a variety.

We prove that for every distributive 〈∨,0〉-semilattice S, there are a meet-semilattice P with zero and a map μ: P × P → S such that μ(x,z) ≤ μ(x,y) ∨ μ(y,z) and x ≤ y implies that μ(x,y) = 0, for all x, y, z ∈ P, together with the following conditions:.

(P1) μ(v,u) = 0 implies that u = v, for all u ≤ v in P.

(P2) For all u ≤ v in P and all a, b ∈ S, if μ(v,u) ≤ a ∨ b, then there are a positive integer n and a decomposition u = x₀ ≤ x₁ ≤ ⋯ ≤ x_n = v such that either μ(x_{i + 1}, x_i) ≤ a or μ(x_i+1, x_i) ≤ b, for each i < n.

(P3) The subset {μ(x,0) | x ∈ P} generates the semilattice S.

Furthermore, every finite, bounded subset of P has a join, and P is bounded in case S is bounded. Furthermore, the construction is functorial on lattice-indexed diagrams of finite distributive 〈∨,0,1〉-semilattices.

We use model theoretic techniques and games to construct explicit first-order axiomatizations for the classes of posets that can be represented as systems of sets, where the order relation is given by inclusion, and existing meets and joins of specified countable cardinalities correspond to intersections and unions, respectively.

$\chi$-Posets and $\chi$-lattices are generalizations of posets and lattices introduced by Juhani Nieminen, where $\chi$ denotes a choice function. In this paper, some new characterizations of $\chi$-lattices and $0,1$-posets are obtained.

For a positive integer n, we denote by SUB (respectively, SUB_n) the class of all lattices that can be embedded into the lattice Co(P) of all order-convex subsets of a partially ordered set P (respectively, P of length at most n). We prove the following results:

(1) SUB_n is a finitely based variety, for any n≥1.

(2) SUB₂ is locally finite.

(3) A finite atomistic lattice L without D-cycles belongs to SUB if and only if it belongs to SUB₂; this result does not extend to the nonatomistic case.

(4) SUB_n is not locally finite for n≥3.