Computability of Distributive Lattices

The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum {d: d ≠ 0}. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively Δ₂⁰-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.     

Relative Projectivity and Transferability for Partial Lattices

A partial lattice P is ideal-projective, with respect to a class \(\mathcal {C}\) of lattices, if for every \(K\in \mathcal {C}\) and every homomorphism φ of partial lattices from P to the ideal lattice of K, there are arbitrarily large choice functions f:P→K for φ that are also homomorphisms of partial lattices. This extends the traditional concept of (sharp) transferability of a lattice with respect to \(\mathcal {C}\). We prove the following: (1) A finite lattice P, belonging to a variety \(\mathcal {V}\), is sharply transferable with respect to \(\mathcal {V}\) iff it is projective with respect to \(\mathcal {V}\) and weakly distributive lattice homomorphisms, iff it is ideal-projective with respect to \(\mathcal {V}\), (2) Every finite distributive lattice is sharply transferable with respect to the class \(\mathcal {R}_{\text {mod}}\) of all relatively complemented modular lattices, (3) The gluing D ₄ of two squares, the top of one being identified with the bottom of the other one, is sharply transferable with respect to a variety \(\mathcal {V}\) iff \(\mathcal {V}\) is contained in the variety \(\mathcal {M}_{\omega }\) generated by all lattices of length 2, (4) D ₄ is projective, but not ideal-projective, with respect to \(\mathcal {R}_{\text {mod}}\) , (5) D ₄ is transferable, but not sharply transferable, with respect to the variety \(\mathcal {M}\) of all modular lattices. This solves a 1978 problem of G. Grätzer, (6) We construct a modular lattice whose canonical embedding into its ideal lattice is not pure. This solves a 1974 problem of E. Nelson.     

Inflation of Finite Lattices Along All-or-nothing Sets

We introduce a new generalization of Alan Day’s doubling construction. For ordered sets \(\mathcal {L}\) and \(\mathcal {K}\) and a subset \(E \subseteq \ \leq _{\mathcal {L}}\) we define the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) arising from inflation of \(\mathcal {L}\) along E by \(\mathcal {K}\). Under the restriction that \(\mathcal {L}\) and \(\mathcal {K}\) are finite lattices, we find those subsets \(E \subseteq \ \leq _{\mathcal {L}}\) such that the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) is a lattice. Finite lattices that can be constructed in this way are classified in terms of their congruence lattices.A finite lattice is binary cut-through codable if and only if there exists a 0?1 spanning chain \(\left \{\theta _{i}\colon 0 \leq i \leq n \right \}\) in \(Con(\mathcal {L})\) such that the cardinality of the largest block of ?? _i /?? _i?1 is 2 for every i with 1≤i≤n. These are exactly the lattices that can be constructed by inflation from the 1-element lattice using only the 2-element lattice. We investigate the structure of binary cut-through codable lattices and describe an infinite class of lattices that generate binary cut-through codable varieties.     

Algebraic Representation of Mappings Between Submodule Lattices

We discuss algebraic representations of mappings preserving arbitrary joins between submodule lattices. For a given join-preserving mapping $ \bar{g}:\mathfrak{L}\left( {_RM} \right)\to \mathfrak{L}\left( {_SN} \right) $ between submodule lattices, a representation is an R-balanced mapping h : B × M → N, where _S B _R is a bimodule such that $ \left\langle {h\left( {B\times U} \right)} \right\rangle =\bar{g}(U) $ for all $ U\in \mathfrak{L}\left( {_RM} \right) $ . We begin by posing the question in a general abstract context and by defining the canonical subrepresentation, which is a representation if and only if there exists a representation. The problem is to give easy and natural conditions for the existence of a representation. We consider a very general situation for the mappings and give sufficient criteria for the existence of a representation. We also consider lattice isomorphisms.     

A Note On Subloop Lattices

Pálfy and Pudlák (Algebra Universalis 11, 22–27, 1980) posed the question: is every finite lattice isomorphic to an interval sublattice of the lattice of subgroups of a finite group? in this paper we will look at examples of lattices that can be realized as subloop lattices but not as subgroup lattices. This is a first step in answering a new question: is every finite lattice isomorphic to an interval sublattice of the subloop lattice of a finite loop?     

Isometrical Embeddings of Lattices into Geometric Lattices

A lattice is said to be finite height generated if it is complete and every element is the join of some elements of finite height. Extending former results by Grätzer and Kiss (Order 2:351–365, 1986) on finite lattices, we prove that every finite height generated algebraic lattice that has a pseudorank function is isometrically embeddable into a geometric lattice.     

Diamond-Free Subsets in the Linear Lattices

Four distinct elements a, b, c, and d of a poset form a diamond if \(a< b and \(a . A subset of a poset is diamond-free if no four elements of the subset form a diamond. Even in the Boolean lattices, finding the size of the largest diamond-free subset remains an open problem. In this paper, we consider the linear lattices—poset of subspaces of a finite dimensional vector space over a finite field of order q—and extend the results of Griggs et al. (J. Combin. Theory Ser. A 119(2):310–322, 2012) on the Boolean lattices, to prove that the number of elements of a diamond-free subset of a linear lattice can be no larger than \(2+\frac {1}{q+1}\) times the width of the lattice, so that this fraction tends to 2 as \(q \longrightarrow \infty \) . In addition, using an algebraic technique, we introduce so-called diamond matchings, and prove that for linear lattices of dimensions up to 5, the size of a largest diamond-free subset is equal to the sum of the largest two rank numbers of the lattice.     

Spline Methods Using Integration Lattices and Digital Nets

Splines are minimum-norm approximations of functions that interpolate the given data (x _l ,f(x _l )),l=0,…,N?1. This paper considers spline approximations to functions in certain reproducing kernel Hilbert spaces, with special choices of the designs {x _l ,l=0,…,N?1}. The designs considered here are node sets of integration lattices and digital nets, and the domain of the functions to be approximated, f is the d-dimensional unit cube. The worst-case errors (in the L _∞ norm) of the splines are shown to depend on the smoothness or digital smoothness of the functions being approximated. Although the convergence rates may be less than ideal, the algorithms are constructive and they do not suffer from a curse of dimensionality.     

Embedding Finite Lattices into Finite Biatomic Lattices

For a class C of finite lattices, the question arises whether any lattice in C can be embedded into some atomistic, biatomic lattice in C. We provide answers to the question above for C being, respectively,– the class of all finite lattices;– the class of all finite lower bounded lattices (solved by the first author's earlier work);– the class of all finite join-semidistributive lattices (this problem was, until now, open).We solve the latter problem by finding a quasi-identity valid in all finite, atomistic, biatomic, join-semidistributive lattices but not in all finite join-semidistributive lattices.     

On Lattices Embeddable into Lattices of Order-Convex Sets. II Star-like Posets

We find a syntactic characterization of the class \(\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}\) of finite lattices embeddable into convexity lattices of a certain class of posets which we call star-like posets and which is a proper subclass in the class of N-free posets. The characterization implies that the class \(\mathrm{\mathbf{SUB}}(\mathcal{S})\cap\mathrm{Fin}\) forms a pseudovariety.     

Lattices of Order-Convex Sets of Forests

We give a characterization of the class Co(F)\mathbf{Co}(\mathcal{F}) [Co(F_n)\mathrm{\mathbf{Co}}(\mathcal{F}_n), n < ω, respectively] of lattices isomorphic to convexity lattices of posets which are forests [forests of length at most n, respectively], as well as of the class Co(L)\mathbf{Co}(\mathcal{L}) of lattices isomorphic to convexity lattices of linearly ordered posets. This characterization yields that the class of finite members from Co(F)\mathbf{Co}(\mathcal{F}) [from Co(F_n)\mathbf{Co}(\mathcal{F}_n), n < ω, or from Co(L)\mathbf{Co}(\mathcal{L})] is finitely axiomatizable within the class of finite lattices.     

Lattices generated by joins of the flats in orbits under finite affine-singular symplectic group and its characteristic polynomials

Let ASG(2ν + l, ν;F _q ) be the (2ν + l)-dimensional affine-singular symplectic space over the finite field F _q and ASp_2ν+l,ν (F _q ) be the affine-singular symplectic group of degree 2ν + l over F _q . Let O be any orbit of flats under ASp_2ν+l,ν (F _q ). Denote by L ^J the set of all flats which are joins of flats in O such that O ? L ^J and assume the join of the empty set of flats in ASG(2ν + l, ν;F _q ) is ?. Ordering L ^J by ordinary or reverse inclusion, then two lattices are obtained. This paper firstly studies the inclusion relations between different lattices, then determines a characterization of flats contained in a given lattice L ^J , when the lattices form geometric lattice, lastly gives the characteristic polynomial of L ^J .     

Interval Dismantlable Lattices

A finite lattice is interval dismantlable if it can be partitioned into an ideal and a filter, each of which can be partitioned into an ideal and a filter, etc., until you reach 1-element lattices. In this note, we find a quasi-equational basis for the pseudoquasivariety of interval dismantlable lattices, and show that there are infinitely many minimal interval non-dismantlable lattices.     

Boolean Lattices: Ramsey Properties and Embeddings

A subposet Q ^′ of a poset Q is a copy of a poset P if there is a bijection f between elements of P and Q ^′ such that x ≤ y in P iff f(x) ≤ f(y) in Q. For posets P, P ^′, let the poset Ramsey number R(P, P ^′) be the smallest N such that no matter how the elements of the Boolean lattice Q _N are colored red and blue, there is a copy of P with all red elements or a copy of P ^′ with all blue elements. We provide some general bounds on R(P, P ^′) and focus on the situation when P and P ^′ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of Q _n in Q _N and for a multicolor version of a poset Ramsey number.     

Laskerian Lattices

In this paper we investigate prime divisors, B _w-primes and zs-primes in C-lattices. Using them some new characterizations are given for compactly packed lattices. Next, we study Noetherian lattices and Laskerian lattices and characterize Laskerian lattices in terms of compactly packed lattices.     

Slim Semimodular Lattices. II. A Description by Patchwork Systems

Rectangular lattices are special planar semimodular lattices introduced by G. Grätzer and E. Knapp in Acta Sci Math 75:29–48, 2009. A patch lattice is a rectangular lattice whose weak corners are coatoms. As a variant of gluing, we introduce the concept of a patchwork system. We prove that every glued sum indecomposable, planar, semimodular lattice is a patchwork of its maximal patch lattice intervals. For a planar modular lattice, our patchwork system is the same as the S-glued system introduced by C. Herrmann in Math Z 130:255–274, 1973. Among planar semimodular lattices, patch lattices are characterized as the patchwork-irreducible ones. They are also characterized as the indecomposable ones with respect to gluing over chains; this gives another structure theorem.     

Some Structure Theorems for Atomistic Algebraic Lattices

We prove that any atomistic algebraic lattice is a direct product of subdirectly irreducible lattices iff its congruence lattice is an atomic Stone lattice. We define on the set A(L) of all atoms of an atomistic algebraic lattice L a relation R as follows: for a, b A(L), (a, b) R ? θ(0, a) ∧ θ(0, b) ≠ ?_{Con L} . We prove that Con L is a Stone lattice iff R is transitive and we give a characterization of Cen (L) using R. We also give a characterization of weakly modular atomistic algebraic lattices.     

Lattices with Defining Relations Close to Distributivity

We consider the 3-generated lattices whose generators enjoy the defining relations of the type a∨(b∧c) = (a∨b)∧(a∨c). Moreover, if the lattice is finite then we obtain its diagram; otherwise, we prove that the corresponding lattice is infinite.     

On the Geometry of Cyclic Lattices

Cyclic lattices are sublattices of \(\mathbb Z^N\) that are preserved under the rotational shift operator. Cyclic lattices were introduced by Micciancio (FOCS, IEEE Computer Society, pp 356–365, 2002) and their properties were studied in the recent years by several authors due to their importance in cryptography. In particular, Peikert and Rosen (Theory of Cryptography, Lecture Notes in Computer Science, vol 3876. Springer, Berlin, pp 145–166, 2006) showed that on cyclic lattices in prime dimensions, the shortest independent vectors problem SIVP reduces to the shortest vector problem SVP with a particularly small loss in approximation factor, as compared to general lattices. In this paper, we further investigate geometric properties of cyclic lattices, proving that a positive proportion of them in every dimension is well-rounded. One implication of our main result is that SVP is equivalent to SIVP on a positive proportion of cyclic lattices in every dimension. As an example, we demonstrate an explicit construction of a family of cyclic lattices on which this equivalence holds. To conclude, we introduce a class of sublattices of \(\mathbb Z^N\) closed under the action of subgroups of the permutation group \(S_N\) , which are a natural generalization of cyclic lattices, and show that our results extend to all such lattices closed under the action of any \(N\) -cycle.     

Lattices of equivalence relations closed under the operations of relation algebras

One of the longstanding problems in universal algebra is the question of which finite lattices are isomorphic to the congruence lattices of finite algebras. This question can be phrased as which finite lattices can be represented as lattices of equivalence relations on finite sets closed under certain first-order formulas. We generalize this question to a different collection of first-order formulas, giving examples to demonstrate that our new question is distinct. We then note that every lattice M _n can be represented in this new way.