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.     

How small can a lattice of order-dimension n be?

The aim of this paper is to study the order-dimension of partition lattices and linear lattices. Our investigations were motivated by a question due to Bill Sands: For a lattice L, does dim L=n always imply |L|≥2 ⁿ ? We will answer this question in the negative since both classes of lattices mentioned above form counterexamples. In the case of the partition lattices, we will determine the dimension up to an absolute constant. For the linear lattice over GF(2), L _n , we determine the dimension up to a factor C/n for an absolute constant C.     

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.     

Extension theorems for linear lattices with positive algebraic basis

An ordered linear spaceV with positive wedgeK is said to satisfy extension property (E1) if for every subspaceL ₀ ofV such thatL ₀ ∩K is reproducing inL ₀, and every monotone linear functionalf ₀ defined onL ₀,f ₀ has a monotone linear extension to all ofV. A linear latticeX is said to satisfy extension property (E2) if for every sublatticeL ofX, and every linear functionalf defined onL which is a lattice homomorphism,f has an extensionf′ to all ofX which is also a linear functional and a lattice homomorphism. In this paper it is shown that a linear lattice with a positive algebraic basis has both extension property (E1) and (E2). In obtaining this result it is shown that the linear span of a lattice idealL and an extremal element not inL is again a lattice ideal. (HereX does not have to have a positive algebraic basis.) It is also shown that a linear lattice which possesses property (E2) must be linearly and lattice isomorphic to a functional lattice. An example is given of a function lattice which has property (E2) but does not have a positive algebraic basis. Yudin [12] has shown a reproducing cone in ann-dimensional linear lattice to be the intersection of exactlyn half-spaces. Here it is shown that the positive wedge in ann-dimensional archimedean ordered linear space satisfying the Riesz decomposition property must be the intersection ofn half-spaces, and hence the space must be a linear lattice with a positive algebraic basis. The proof differs from those given for the linear lattice case in that it uses no special techniques, only well known results from the theory of ordered linear space.     

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.     

The lattice of integer partitions

In this paper we study the lattice L_n of partitions of an integer n ordered by dominance. We show L_n to be isomorphic to an infimum subsemilattice under the component ordering of certain concave nondecreasing (n+1)-tuples. For L_n, we give the covering relation, maximal covering number, minimal chains, infimum and supremum irreducibles, a chain condition, distinguished intervals; and show that partition conjugation is a lattice antiautomorphism. L_n is shown to have no sublattice having five elements and rank two, and we characterize intervals generated by two cocovers. The Möbius function of L_n is computed and shown to be 0,1 or -1. We then give methods for studying classes of (0,1)-matrices with prescribed row and column sums and compute a lower bound for their cardinalities.     

On the Order Dimension of Convex Geometries

We study the order dimension of the lattice of closed sets for a convex geometry. We show that the lattice of closed subsets of the planar point set of Erd?s and Szekeres from 1961, which is a set of 2 ^n???2 points and contains no vertex set of a convex n-gon, has order dimension n???1 and any larger set of points has order dimension at least n.     

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.     

Note on the description of join-distributive lattices by permutations

Let L be a join-distributive lattice with length n and width(JiL) ≤ k. There are two ways to describe L by k ? 1 permutations acting on an n-element set: a combinatorial way given by P.H. Edelman and R. E. Jamison in 1985 and a recent lattice theoretical way of the second author. We prove that these two approaches are equivalent. Also, we characterize join-distributive lattices by trajectories.     

Cohomology of a class of Kadison-Singer algebras

Let L be the complete lattice generated by a nest N on an infinite-dimensional separable Hilbert space H and a rank one projection P ξ given by a vector ξ in H. Assume that ξ is a separating vector for N , the core of the nest algebra Alg(N ). We show that L is a Kadison-Singer lattice, and hence the corresponding algebra Alg(L) is a Kadison-Singer algebra. We also describe the center of Alg(L) and its commutator modulo itself, and show that every bounded derivation from Alg(L) into itself is inner, and all n-th bounded cohomology groups H n (Alg(L), B(H)) of Alg(L) with coefficients in B(H) are trivial for all n≥1.     

Embedding and unsolvability theorems for modular lattices

LetR be a nontrivial ring with 1 and δ a cardinal. Let,L(R, δ) denote the lattice of submodules of a free unitaryR-module on δ generators. Let ? be the variety of modular lattices. A lattice isR-representable if embeddable in the lattice of submodules of someR-module; ?(R) denotes the quasivariety of allR-representable lattices. Let ω denote aleph-null, and let a (m, n) presentation havem generators andn relations,m, n≤ω. THEOREM. There exists a (5, 1) modular lattice presentation having a recursively unsolvable word problem for any quasivarietyV,V ? ?, such thatL(R, ω) is inV. THEOREM. IfL is a denumerable sublattice ofL(R, δ), then it is embeddable in some sublatticeK ofL(R,δ^*) having five generators, where δ^*=δ for infinite δ and δ^*=4δ(m+1) if δ is finite andL has a set ofm generators. THEOREM. The free ?(R)-lattice on ω generators is embeddable in the free ?(R)-lattice on five generators. THEOREM. IfL has an (m, n), ?(R)-presentation for denumerablem and finiten, thenL is embeddable in someK having a (5, 1) ?(R)-presentation.     

The spectrum of a finite pseudocomplemented lattice

Let L be a finite pseudocomplemented lattice. Every interval [0, a] in L is pseudocomplemented, so by Glivenko’s theorem, the set S(a) of all pseudocomplements in [0, a] forms a boolean lattice. Let B _i denote the finite boolean lattice with i atoms. We describe all sequences (s ₀, s ₁, . . . , s _n ) of integers for which there exists a finite pseudocomplemented lattice L with s _i = |{ a ∈ L | S(a) ? B _i }|, for all i, and there is no a ∈ L with S(a) ? B _n+1. This result settles a problem raised by the first author in 1971.     

Further characterizations of cubic lattice graphs

A cubic lattice graph with characteristic n is a graph whose points can be identified with the ordered triplets on n symbols and two points are adjacent whenever the corresponding triplets have two coordinates in common. An L₂ graph is a graph whose points can be identified with the ordered pairs on n symbols such that two points are adjacent if and only if the corresponding pairs have a common coordinate. The main result of this paper is two new characterizations and shows the relation between cubic lattice and L₂ graphs. The main result also suggests a conjecture concerning the characterization of interchange graphs of complete m-partite graphs.     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

A Method of Deducing L-Polyhedra for n-Lattices

We suggest a method for selecting an L-simplex in an L-polyhedron of an n-lattice in Euclidean space. By taking into account the specific form of the condition that a simplex in the lattice is an L-simplex and by considering a simplex selected from an L-polyhedron, we present a new method for describing all types of L-polyhedra in lattices of given dimension n. We apply the method to deduce all types of L-polyhedra in n-dimensional lattices for n=2,3,4, which are already known from previous results.     

Multidimensional Farey partitions

The linear action of SL(n, ?₊) induces lattice partitions on the (n − 1)-dimensional simplex †n−1. The notion of Farey partition raises naturally from a matricial interpretation of the arithmetical Farey sequence of order r. Such sequence is unique and, consequently, the Farey partition of order r on A 1 is unique. In higher dimension no generalized Farey partition is unique. Nevertheless in dimension 3 the number of triangles in the various generalized Farey partitions is always the same which fails to be true in dimension n > 3. Concerning Diophantine approximations, it turns out that the vertices of an n-dimensional Farey partition of order r are the radial projections of the lattice points in ?₊ⁿ ∩ [0, r]ⁿ whose coordinates are relatively prime. Moreover, we obtain sequences of multidimensional Farey partitions which converge pointwisely.     

Cutoff for the Ising model on the lattice

Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L ¹ on a system of size n is O(logn). Whether in this regime there is cutoff, i.e. a sharp transition in the L ¹-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1))logn for some fixed c>0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem. We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For ?² this carries all the way to the critical temperature. Specifically, for fixed d≥1, the continuous-time Glauber dynamics for the Ising model on (?/n?) ^d with periodic boundary conditions has cutoff at (d/2λ _∞)logn, where λ _∞ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited. The proof hinges on a new technique for translating L ¹-mixing to L ²-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.     

On certain spaces of lattice diagram determinants

The aim of this work is to study some lattice diagram determinants Δ_L(X,Y) as defined in (Adv. Math. 142 (1999) 244) and to extend results of Aval et al. (J. Combin. Theory Ser. A, to appear). We recall that M_L denotes the space of all partial derivatives of Δ_L. In this paper, we want to study the space M_i,j^k(X,Y) which is defined as the sum of M_L spaces where the lattice diagrams L are obtained by removing k cells from a given partition, these cells being in the “shadow” of a given cell (i,j) in a fixed Ferrers diagram. We obtain an upper bound for the dimension of the resulting space M_i,j^k(X,Y), that we conjecture to be optimal. This dimension is a multiple of n! and thus we obtain a generalization of the n! conjecture. Moreover, these upper bounds associated to nice properties of some special symmetric differential operators (the “shift” operators) allow us to construct explicit bases in the case of one set of variables, i.e. for the subspace M_i,j^k(X) consisting of elements of 0 Y-degree.     

Shifted lattice rules based on a general weighted discrepancy for integrals over Euclidean space

We approximate weighted integrals over Euclidean space by using shifted rank-1 lattice rules with good bounds on the “generalised weighted star discrepancy”. This version of the discrepancy corresponds to the classic L_∞ weighted star discrepancy via a mapping to the unit cube. The weights here are general weights rather than the product weights considered in earlier works on integrals over R^d. Known methods based on an averaging argument are used to show the existence of these lattice rules, while the component-by-component technique is used to construct the generating vector of these shifted lattice rules. We prove that the bound on the weighted star discrepancy considered here is of order O(n^−1+δ) for any δ>0 and with the constant involved independent of the dimension. This convergence rate is better than the O(n^−1/2) achieved so far for both Monte Carlo and quasi-Monte Carlo methods.     

The level polynomials of the free distributive lattices

We show that there exist a set of polynomials {L_k?k = 0, 1?} such that L_k(n) is the number of elements of rank k in the free distributive lattice on n generators. L₀(n) = L₁(n) = 1 for all n and the degree of L_k is k?1 for k?1. We show that the coefficients of the L_k can be calculated using another family of polynomials, P_j. We show how to calculate L_k for k = 1,…,16 and P_j for j = 0,…,10. These calculations are enough to determine the number of elements of each rank in the free distributive lattice on 5 generators a result first obtained by Church [2]. We also calculate the asymptotic behavior of the L_k's and P_j's.