Valuations and closure operators on finite lattices

Let L be a lattice. A function f:L→R (usually called evaluation) is submodular if f(x∧y)+f(x∨y)≤f(x)+f(y), supermodular if f(x∧y)+f(x∨y)≥f(x)+f(y), and modular if it is both submodular and supermodular. Modular functions on a finite lattice form a finite dimensional vector space. For finite distributive lattices, we compute this (modular) dimension. This turns out to be another characterization of distributivity (Theorem 3.9). We also present a correspondence between isotone submodular evaluations and closure operators on finite lattices (Theorem 5.5). This interplay between closure operators and evaluations should be understood as building a bridge between qualitative and quantitative data analysis.     

A subclass of Ockham algebras

Here we introduce a subclass of the class of Ockham algebras ( L ; f ) for which L satisfies the property that for every x ∈ L , there exists n ≥ 0 such that fn ( x ) and fn+1 ( x ) are complementary. We characterize the structure of the lattice of congruences on such an algebra ( L ; f ). We show that the lattice of compact congruences on L is a dual Stone lattice, and in particular, that the lattice Con L of congruences on L is boolean if and only if L is finite boolean. We also show that L is congruence coherent if and only if it is boolean. Finally, we give a sufficient and necessary condition to have the subdirectly irreducible chains.     

Varieties of Lattices with Geometric Descriptions

A lattice L is spatial if every element of L is a join of completely join-irreducible elements of L (points), and strongly spatial if it is spatial and the minimal coverings of completely join-irreducible elements are well-behaved. Herrmann et al. proved in 1994 that every modular lattice can be embedded, within its variety, into an algebraic and spatial lattice. We extend this result to n-distributive lattices, for fixed n. We deduce that the variety of all n-distributive lattices is generated by its finite members, thus it has a decidable word problem for free lattices. This solves two problems stated by Huhn in 1985. We prove that every modular (resp., n-distributive) lattice embeds within its variety into some strongly spatial lattice. Every lattice which is either algebraic modular spatial or bi-algebraic is strongly spatial. We also construct a lattice that cannot be embedded, within its variety, into any algebraic and spatial lattice. This lattice has a least and a largest element, and it generates a locally finite variety of join-semidistributive lattices.     

On the irreducibility of a class of polynomials,III

This work is a continuation and extension of our earlier articles on irreducible polynomials. We investigate the irreducibility of polynomials of the form g(f(x)) over an arbitrary but fixed totally real algebraic number field $\text{L}$, where g(x) and f(x) are monic polynomials with integer coefficients in $\text{L}$, g is irreducible over $\text{L}$ and its splitting field is a totally imaginary quadratic extension of a totally real number field. A consequence of our main result is as follows. If g is fixed then, apart from certain exceptions f of bounded degree, g(f(x)) is irreducible over $\text{L}$ for all f having distinct roots in a given totally real number field.     

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.     

The rank of a distributive lattice

The rank of a partial ordering P is the maximum size of an irredundant family of linear extensions of P whose intersection is P. A simple relationship is established between the rank of a finite distributive lattice and its subset of join irreducible elements.     

Linear transformations of monotone functions on the discrete cube

For a function f:{0,1}ⁿ→R and an invertible linear transformation L∈GL_n(2), we consider the function Lf:{0,1}ⁿ→R defined by Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if f is Boolean and monotone then I(Lf)≥I(f), where I(f) is the total influence of f. Second, we conjecture that if both f and L(f) are monotone, then f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where L is upper triangular.     

Principle of inclusion-exclusion on semilattices

We introduce an enumeration theorem under lattice action. Let L be a finite semilattice and Ω be a nonempty set. Let $\text{f: L → P(Ω)}$ be a map satisfying f(x ? y) ? f(x) ∩ f(y), where ? and $\text{P}$(Ω) mean “join” and the power set of Ω, respectively. Then

$\text{m}\text{∪}\text{x?L}\text{?(x)}\text{=}\text{Σ}\text{c?C}\text{(?1)}{}^{\mathrm{l(c)}}\text{m}\text{∩}\text{x?c}\text{?(x)}$

, where C is the set of all chains in L and l(c) denotes the length of a chain c. Also the theorem can be dualized. Furthermore, we describe two applications of the theorem to a Boolean lattice of sets and a partition lattice of a set.     

Lattice Classification by Cut-through Coding

Inspired by engineering of high-speed switching with quality of service, this paper introduces a new approach to classify finite lattices by the concept of cut-through coding. An n-ary cut-through code of a finite lattice encodes all lattice elements by distinct n-ary strings of a uniform length such that for all j, the initial j encoding symbols of any two elements x and y determine the initial j encoding symbols of the meet and join of x and y. In terms of lattice congruences, some basic criteria are derived to characterize the n-ary cut-through codability of a finite lattice. N-ary cut-through codability also gives rise to a new classification of lattice varieties and in particular, defines a chain of ideals in the lattice of lattice varieties.     

Subdiagrams equal in number to their duals

In the middle 1930's, the early days of combinatorial lattice theory, it had been conjectured thatin any finite modular lattice the number of join-irreducible elements equals the number of meetirreducible elements. The conjecture was settled in 1954 by R. P. Dilworth in a remarkable combinatorial generalization. Quite recently we have been led to this question. Which ordered setsS satisfy the property that,for any modular lattice M, the number of subdiagrams of M isomorphic to S equals the number of subdiagrams of M dually isomorphic to S?     

Modularly complemented geometric lattices

A geometric lattice L is strongly uniform if the quotients [x₁, 1] and [x₂, 1] are isomorphic for all x₁, x₂εL of the same rank. It is shown that if L is a simple geometric lattice in which each element has a modular complement then L is strongly uniform.     

A structure theorem for dismantlable lattices and enumeration

The concept of `adjunct' operation of two lattices with respect to a pair of elements is introduced. A structure theorem namely, `A finite lattice is dismantlable if and only if it is an adjunct of chains' is obtained. Further it is established that for any adjunct representation of a dismantlable lattice the number of chains as well as the number of times a pair of elements occurs remains the same. If a dismantlable lattice L has n elements and n+k edges then it is proved that the number of irreducible elements of L lies between n-2k-2 and n-2. These results are used to enumerate the class of lattices with exactly two reducible elements, the class of lattices with n elements and upto n+1 edges, and their subclasses of distributive lattices and modular lattices. This revised version was published online in June 2006 with corrections to the Cover Date.     

Dimension and automorphism groups of lattices

Every group is the automorphism group of a lattice of order dimension at most 4. We conjecture that the automorphism groups of finite modular lattices of bounded dimension do not represent every finite group. It is shown that ifp is a large prime dividing the order of the automorphism group of a finite modular latticeL then eitherL has high order dimension orM _p, the lattice of height 2 and orderp+2, has a cover-preserving embedding inL. We mention a number of open problems. Presented by C. R. Platt.     

Generalizations of Boolean products for lattice-ordered algebras

It is shown that the Boolean center of complemented elements in a bounded integral residuated lattice characterizes direct decompositions. Generalizing both Boolean products and poset sums of residuated lattices, the concepts of poset product, Priestley product and Esakia product of algebras are defined and used to prove decomposition theorems for various ordered algebras. In particular, we show that FL_w-algebras decompose as a poset product over any finite set of join irreducible strongly central elements, and that bounded n-potent GBL-algebras are represented as Esakia products of simple n-potent MV-algebras.     

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.     

Codimension and pseudometric in co-Heyting algebras

In this paper, we introduce a notion of dimension and codimension for every element of a bounded distributive lattice L. These notions prove to have a good behavior when L is a co-Heyting algebra. In this case the codimension gives rise to a pseudometric on L which satisfies the ultrametric triangle inequality. We prove that the Hausdorff completion of L with respect to this pseudometric is precisely the projective limit of all its finite dimensional quotients. This completion has some familiar metric properties, such as the convergence of every monotonic sequence in a compact subset. It coincides with the profinite completion of L if and only if it is compact or equivalently if every finite dimensional quotient of L is finite. In this case we say that L is precompact. If L is precompact and Hausdorff, it inherits many of the remarkable properties of its completion, specially those regarding the join/meet irreducible elements. Since every finitely presented co-Heyting algebra is precompact Hausdorff, all the results we prove on the algebraic structure of the latter apply in particular to the former. As an application, we obtain the existence for every positive integers n, d of a term t _{n, d} such that in every co-Heyting algebra generated by an n-tuple a, t _{n, d} (a) is precisely the maximal element of codimension d.     

On the Rédei zeta function

Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ?(s; L) = Σ_x∈Lμ(Ô, x) ν(Ô, x)^?s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.     

Reducible classes of finite lattices

In this paper we study a notion of reducibility in finite lattices. An element x of a (finite) lattice L satisfying certain properties is deletable if L-x is a lattice satisfying the same properties. A class of lattices is reducible if each lattice of this class admits (at least) one deletable element (equivalently if one can go from any lattice in this class to the trivial lattice by a sequence of lattices of the class obtained by deleting one element in each step). First we characterize the deletable elements in a pseudocomplemented lattice what allows to prove that the class of pseudocomplemented lattices is reducible. Then we characterize the deletable elements in semimodular, modular and distributive lattices what allows to prove that the classes of semimodular and locally distributive lattices are reducible. In conclusion the notion of reducibility for a class of lattices is compared with some other notions like the notion of order variety.     

Generating sets for lattices of dimension two

The dimension of a partially ordered set P is the smallest integer n (if it exists) such that the partial order on P is the intersection of n linear orders. It is shown that if L is a lattice of dimension two containing a sublattice isomorphic to the modular lattice M_2n+1, then every generating set of L has at least n+2 elements. A consequence is that every finitely generated lattice of dimension two and with no infinite chains is finite.     

A counterexample to the generalization of Sperner's theorem

It has been conjectured that the analog of Sperner's theorem on non-comparable subsets of a set holds for arbitrary geometric lattices, namely, that the maximal number of non-comparable elements in a finite geometric lattice is max w(k), where w(k) is the number of elements of rank k. It is shown in this note that the conjecture is not true in general. A class of geometric lattices, each of which is a bond lattice of a finite graph, is constructed in which the conjecture fails to hold.