The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
G. Grätzer, H. Lakser, and E. T. Schmidt proved that every finite distributive lattice D with n join-irreducible elements can be represented as the congruence lattice of a lattice L with O(n2) elements. G. Grätzer, I. Rival, and N. Zaguia gave knα, α < 2, as a lower bound for the size of such a lattice L; a sharper form, 1/64(n/log2n)2, of this result was given by Y. Zhang. In this note, we apply...
We investigate a new class of Boolean algebra, called initial chain algebras on pseudotrees. We discuss the relationship between this class and other classes of Boolean algebras. Every interval algebra, and hence every countable Boolean algebra, is an initial chain algebra. Every initial chain algebra on a tree is a superatomic Boolean algebra, and every initial chain algebra on a pseudotree is a...
We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.
If each of a set A of l-dimensional faces of an n-dimensional cube is to be represented by a l–b dimensional subface, then it is possible to choose distinct representatives provided the cardinality of A does not exceed a certain bound. We give an algorithm for calculating this bound.
Let k be a positive integer and let P = (X,≤) be a poset. We call P a k-sphere order provided there is a mapping f which assigns to each element x $$ \in$$ X a ball f(x) in Rk so that x ≤ y in P if and only if f(x) $$ \subseteq$$ f(y). We ask: Given that P is a k-sphere order, does there necessarily exist a representation f with the property that every minimal element of P is assigned a...
An additive sequence of integers is a finite sequence in which the sum of any number of consecutive terms is less than or equal to the sum of the same number of initial terms in the sequence and greater than or equal to the sum of the same number of final terms in the sequence. If the final several terms in an additive sequence are greater than or equal to, in order, the initial several terms of a...
For any ordered set P, the join dense completions of P form a complete lattice K(P) with least element O(P), the lattice of order ideals of P, and greatest element M(P), the Dedekind–MacNeille completion P. The lattice K(P) is isomorphic to an ideal of the lattice of all closure operators on the lattice O(P). Thus it inherits some local structural properties which hold in the lattice of closure operators...
We construct uncountable graphs in which any two isomorphic subgraphs of size at most 3 can be carried one to the other by an automorphism of the graph, but in which some isomorphism between 2-element subsets does not extend to an automorphism. The corresponding phenomenon does not occur in the countable case. The construction uses a suitable construction of infinite homogeneous coloured chains.
Let Ln(q) denote the lattice of subspaces of ann-dimensional vector space over the finite field of q elements, ordered byinclusion. In this note, we prove that for all n and m the minimum cutsetfor an element A with $$\dim (A) = m{\text{ of }}L_n (q)$$ is justL(A) if m < n/ 2, is U(A) if m > n/ 2, and both L(A) andU(A) if m = n/ 2, where L(A) is the collection of all $$X \in {\text{...
The free distributive completion of a partial complete lattice is the complete lattice that it is freely generated by the partial complete lattice ‘in the most distributive way’. This can be described as being a universal solution in the sense of universal algebra. Free distributive completions generalize the constructions of tensor products and of free completely distributive complete lattices over...
The class of width-two orders has a model companion. The model companion is complete, decidable, non-finitely axiomatizable, and has continuum many countable models. Generalizations of some results in (Pouzet, M., 1978, J. Combin. Theory Ser. B 25) are presented in the width-n case, for n2.
The fixed point property for finite posets of width 3 and 4 is studied in terms of forbidden retracts. The ranked forbidden retracts for width 3 and 4 are determined explicitly. The ranked forbidden retracts for the width 3 case that are linearly indecomposable are examined to see which are minimal automorphic. Part of a problem of Niederle from 1989 is thus solved.
A poset P=(X,P) is a split semiorder when there exists a function I thatassigns to each x ∈ X a closed interval $$I(x) = [a_x ,a_x + 1]$$ of the real line R and a set $$F = \{ f_x :x \in X\} $$ of real numbers, with $$a_x \leqslant f_x \leqslant a_x + 1$$ , suchthat x<y in P if and only if $$f_x < a_y $$ and $$a_x + 1 < f_y $$ in R. Every semiorder is a split semiorder,...
Addive partial orders arise naturally in theories of comparativeprobability and subset preferences. An additive partial order is a partialorder ≻ on the family of subsets of ann-element set that satisfies $$A \succ B \Leftrightarrow A\backslash B \succ B\backslash A$$ . This is reformulated as a subset P of {1,0,−1}n that excludes 0 and containsx+y whenever x,y ∈ P and x+y ∈ {1,0,−1}n. Additional...
The general non preemptive multiprocessor scheduling problem (NPMS) is NP-Complete, while in many specific cases, the same problem is Time-polynomial. A first connection between PMS and linear programming was established by Yannanakis, Sauer and Stone, who associated to any PMS instance some specific linear program. The main result inside this paper consists in a characterization of the partially...
We present a summary of recent NP-hardness and polynomial time solvability results for the distinction between ‘strong’ and ‘weak’ precedence for chains and trees in scheduling. We distinguish between chains and proper trees which are not chains, and demonstrate that the strong-weak precedence distinction for chains is not inclusive with regards to NP-hardness, and conjecture that the same holds for...
The order dimension of suborders of the Boolean lattice $$B_n $$ is considered. It is shown that the suborder of $$B_n $$ consisting of levels s and s+1 has dimension O(\log n/log log n). This improves a bound in [1].
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.