Cambrian lattices

For an arbitrary finite Coxeter group W, we define the family of Cambrian lattices for W as quotients of the weak order on W with respect to certain lattice congruences. We associate to each Cambrian lattice a complete fan, which we conjecture is the normal fan of a polytope combinatorially isomorphic to the generalized associahedron for W. In types A and B we obtain, by means of a fiber-polytope construction, combinatorial realizations of the Cambrian lattices in terms of triangulations and in terms of permutations. Using this combinatorial information, we prove in types A and B that the Cambrian fans are combinatorially isomorphic to the normal fans of the generalized associahedra and that one of the Cambrian fans is linearly isomorphic to Fomin and Zelevinsky's construction of the normal fan as a “cluster fan.” Our construction does not require a crystallographic Coxeter group and therefore suggests a definition, at least on the level of cellular spheres, of a generalized associahedron for any finite Coxeter group. The Tamari lattice is one of the Cambrian lattices of type A, and two “Tamari” lattices in type B are identified and characterized in terms of signed pattern avoidance. We also show that open intervals in Cambrian lattices are either contractible or homotopy equivalent to spheres.     

Factoring Polynomials and the Knapsack Problem

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f. This exponential time complexity is due to a combinatorial problem: the problem of choosing the right subsets of these n factors. In this paper, this combinatorial problem is reduced to a type of Knapsack problem that can be solved with lattice reduction algorithms. The result is a practical algorithm that can factor polynomials that are far out of reach for previous algorithms. The presented solution to the combinatorial problem is different from previous lattice-based factorizers; these algorithms avoided the combinatorial problem by solving the entire factorization problem with lattice reduction. This led to lattices of large dimension and coefficients, and thus poor performance. This is why lattice-based algorithms, despite their polynomial time complexity, did not replace Berlekamp-Zassenhaus as the standard method. That is now changing; new versions of computer algebra systems such as Maple, Magma, NTL and Pari have already switched to the algorithm presented here.     

On the category of lattice-valued bornological vector spaces

Motivated by the theory of L-bornological spaces of M. Abel and A. Šostak over a complete lattice L, and the concept of topological system of S. Vickers, this paper introduces the categories of L-bornological vector spaces and systems, and shows that the former is isomorphic to a full reflective subcategory of the latter.     

The finite-dimensional modular Lie superalgebra Ω

The finite-dimensional modular Lie superalgebra Ω is constructed. The simplicity of Ω is proved. Its derivation superalgebra is determined. Then it is obtained that Ω is not isomorphic to any known Z-graded modular Lie superalgebra of Cartan type.     

A cover-preserving embedding of semimodular lattices into geometric lattices

Extending former results by G. Grätzer and E.W. Kiss (1986) [5] and M. Wild (1993) [9] on finite (upper) semimodular lattices, we prove that each semimodular lattice L of finite length has a cover-preserving embedding into a geometric lattice G of the same length. The number of atoms of our G equals the number of join-irreducible elements of L.     

Non-representable distributive semilattices

We present two examples of distributive algebraic lattices which are not isomorphic to the congruence lattice of any lattice. The first such example was discovered by F. Wehrung in 2005. One of our examples is defined topologically, the other one involves majority algebras. In particular, we prove that the congruence lattice of the free majority algebra on (at least) ℵ₂ generators is not isomorphic to the congruence lattice of any lattice. Our method is a generalization of Wehrung’s approach, so that we are able to apply it to a larger class of distributive semilattices.     

A solution to Dilworth's congruence lattice problem

We construct an algebraic distributive lattice D that is not isomorphic to the congruence lattice of any lattice. This solves a long-standing open problem, traditionally attributed to R.P. Dilworth, from the forties. The lattice D has a compact top element and ℵω+1 compact elements. Our results extend to any algebra possessing a congruence-compatible structure of a join-semilattice with a largest element.     

The uniquely embeddable planar graphs

Whitney [7] proved in 1932 that for any two embeddings of a planar 3-connected graph, their combinatorial duals are isomorphic. In this manner, the term “uniquely embeddable planar graph” was introduced. It is a well-known fact that combinatorial and geometrical duals are equivalent concepts. In this paper, the concept of unique embeddability is introduced in terms of special types of isomorphisms between any two embeddings of a planar graph. From this, the class U of all graphs which are uniquely embeddable in the plane according to this definition, is determined, and the planar 3-connected graphs are a proper subset of U. It turns out that the graphs in U have a unique geometrical dual (i.e., for any two embeddings of such a graph, their geometrical duals are isomorphic). Furthermore, the theorems and their proofs do not involve any type of duals.     

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.     

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.     

Coordinatization of lattices by regular rings without unit and Banaschewski functions

A Banaschewski function on a bounded lattice L is an antitone self-map of L that picks a complement for each element of L. We prove a set of results that include the following:

• Every countable complemented modular lattice has a Banaschewski function with Boolean range, the latter being unique up to isomorphism.
• Every (not necessarily unital) countable von Neumann regular ring R has a map ${\varepsilon}$ from R to the idempotents of R such that ${x{R} = \varepsilon(x){R}}$ and ${\varepsilon(xy) = \varepsilon(x)\varepsilon(xy)\varepsilon(x)}$ for all ${x, y \in R}$ .
• Every sectionally complemented modular lattice with a Banaschewski trace (a weakening of the notion of a Banaschewski function) embeds, as a neutral ideal and within the same quasivariety, into some complemented modular lattice. This applies, in particular, to any sectionally complemented modular lattice with a countable cofinal subset.

A sectionally complemented modular lattice L is coordinatizable, if it is isomorphic to the lattice ${\mathbb{L}(R)}$ of all principal right ideals of a von Neumann regular (not necessarily unital) ring R. We say that L has a large 4-frame, if it has a homogeneous sequence (a ₀, a ₁, a ₂, a ₃) such that the neutral ideal generated by a ₀ is L. Jónsson proved in 1962 that if L has a countable cofinal sequence and a large 4-frame, then it is coordinatizable. We prove that A sectionally complemented modular lattice with a large 4-frame is coordinatizable iff it has a Banaschewski trace.     

Lebesgue decomposition and bartle—dunford—schwartz theorem in pseudo-D-lattices

Let L be a pseudo-D-lattice. We prove that the exhaustive lattice uniformities on L which makes the operations of L uniformly continuous form a Boolean algebra isomorphic to the centre of a suitable complete pseudo-D-lattice associated to L. As a consequence, we obtain decomposition theorems—such as Lebesgue and Hewitt—Yosida decompositions—and control theorems—such as Bartle—Dunford—Schwartz and Rybakov theorems—for modular measures on L.     

On a partition identity of Lehmer

Euler's identity equates the number of partitions of any non-negative integer n into odd parts and the number of partitions of n into distinct parts. Beck conjectured and Andrews proved the following companion to Euler's identity: the excess of the number of parts in all partitions of n into odd parts over the number of parts in all partitions of n into distinct parts equals the number of partitions of n with exactly one even part (possibly repeated). Beck's original conjecture was followed by generalizations and so-called “Beck-type” companions to other identities.In this paper, we establish a collection of Beck-type companion identities to the following result mentioned by Lehmer at the 1974 International Congress of Mathematicians: the excess of the number of partitions of n with an even number of even parts over the number of partitions of n with an odd number of even parts equals the number of partitions of n into distinct, odd parts. We also establish various generalizations of Lehmer's identity, and prove related Beck-type companion identities. We use both analytic and combinatorial methods in our proofs.     

Extensions of regular polytopes with preassigned Schläfli symbol

We say that a (d+1)-polytope P is an extension of a polytope K if the facets or the vertex figures of P are isomorphic to K. The Schläfli symbol of any regular extension of a regular polytope is determined except for its first or last entry. For any regular polytope K we construct regular extensions with any even number as first entry of the Schläfli symbol. These extensions are lattices if K is a lattice. Moreover, using the so-called CPR graphs we provide a more general way of constructing extensions of polytopes.     

A Distributive Lattice Structure Connecting Dyck Paths,Noncrossing Partitions and 312-avoiding Permutations

In [Ferrari, L. and Pinzani, R.: Lattices of lattice paths. J. Stat. Plan. Inference 135 (2005), 77–92] a natural order on Dyck paths of any fixed length inducing a distributive lattice structure is defined. We transfer this order to noncrossing partitions along a well-known bijection [Simion, R.: Noncrossing partitions. Discrete Math. 217 (2000), 367–409], thus showing that noncrossing partitions can be endowed with a distributive lattice structure having some combinatorial relevance. Finally we prove that our lattices are isomorphic to the posets of 312-avoiding permutations with the order induced by the strong Bruhat order of the symmetric group.     

Excluded–Minor Characterizations of Antimatroids arisen from Posets and Graph Searches

An antimatroid is a family of sets such that it contains an empty set, and it is accessible and closed under union of sets. An antimatroid is a ’dual’ or ‘antipodal’ concept of matroid.We shall show that an antimatroid is derived from shelling of a poset if and only if it does not contain a minor isomorphic to S₇ where S₇ is the smallest semimodular lattice that is not modular (See Fig. 1). It is also shown that an antimatroid is a node-search antimatroid of a digraph if and only if it does not contain a minor isomorphic to D₅ where D₅ is a lattice consisting of five elements Ø {x},{y}, {x, y} and {x, y, z}. Furthermore, an antimatroid is shown to be a node-search antimatroid of an undirected graph if and only if it does not contain D₅ nor S₁₀ as a minor: S₁₀ is a locally free lattice consisting of ten elements shown in Fig. 2.     

On the Schröder–Bernstein property for modules

The well known Schröder–Bernstein Theorem states that any two sets with one to one maps into each other are isomorphic. The question of whether any two (subisomorphic or) direct summand subisomorphic algebraic structures are isomorphic, has long been of interest. Kaplansky asked whether direct summands subisomorphic abelian groups are always isomorphic? The question generated a great deal of interest. The study of this question for the general class of modules has been somewhat limited. We extend the study of this question for modules in this paper. We say that a module Msatisfies the Schröder–Bernstein property (S-B property) if any two direct summands of M which are subisomorphic to direct summands of each other, are isomorphic. We show that a large number of classes of modules satisfy the S-B property. These include the classes of quasi-continuous, directly finite, quasi-discrete and modules with ACC on direct summands. It is also shown that over a Noetherian ring R, every extending module satisfies the S-B property. Among applications, it is proved that the class of rings R for which every R-module satisfies the S-B property is precisely that of pure-semisimple rings. We show that over a commutative domain R, any two quasi-continuous subisomorphic R-modules are isomorphic if and only if R is a PID. We study other conditions related to the S-B property and obtain characterizations of certain classes of rings via those conditions. Examples which delimit and illustrate our results are provided.     

Automorphisms of the lattice of all subalgebras of the semiring of polynomials in one variable

In this paper, we describe automorphisms of the lattice $ {\mathbb A} $ of all subalgebras of the semiring ?⁺[x] of polynomials in one variable over the semifield ?⁺ of nonnegative real numbers. It is proved that any automorphism of the lattice A is generated by an automorphism of the semiring ?⁺[x] that is induced by a substitution x ? px for some positive real number p. It follows that the automorphism group of the lattice $ {\mathbb A} $ is isomorphic to the group of all positive real numbers with multiplication. A technique of unigenerated subalgebras is applied.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

Hamiltonicity and combinatorial polyhedra

We say that a polyhedron with 0–1 valued vertices is combinatorial if the midpoint of the line joining any pair of nonadjacent vertices is the midpoint of the line joining another pair of vertices. We show that the class of combinatorial polyhedra includes such well-known classes of polyhedra as matching polyhedra, matroid basis polyhedra, node packing or stable set polyhedra and permutation polyhedra. We show the graph of a combinatorial polyhedron is always either a hypercube (i.e., isomorphic to the convex hull of a k-dimension unit cube) or else is hamilton connected (every pair of nodes is the set of terminal nodes of a hamilton path). This implies several earlier results concerning special cases of combinatorial polyhedra.