A generalized permutahedron

With respect to a fixedn-element ordered setP, thegeneralized permutahedron Perm(P) is the set of all ordered setsP L, whereL is any permutation of the elements of the underlyingn-element set. Considered as a subset of the extension lattice of ann-element set,Perm(P) is cover-preserving. We apply this to deduce, for instance, that, in any finite ordered setP, there is a comparability whose removal will not increase the dimension, and there is a comparability whose addition toP will not increase its dimension.We establish further properties about the extension lattice which seem to be of independent interest, leading for example, to the characterization of those ordered setsP for which this generalized permutahedron is itself a lattice.Presented by J. Sichler.Dedicated to the memory of Alan DaySupported in part by PRC Mathématiques-Informatique (France) and NSERC (Canada).Supported in part by DFG (Germany) and NSERC (Canada).Supported in part by NSERC (Canada).     

Congruence lattices of function lattices

Thefunction lattice L ^P is the lattice of all isotone maps from a posetP into a latticeL.D. Duffus, B. Jónsson, and I. Rival proved in 1978 that for afinite poset P, the congruence lattice ofL ^P is a direct power of the congruence lattice ofL; the exponent is |P|.This result fails for infiniteP. However, utilizing a generalization of theL ^P construction, theL[D] construction (the extension ofL byD, whereD is a bounded distributive lattice), the second author proved in 1979 that ConL[D] is isomorphic to (ConL) [ConD] for afinite lattice L.In this paper we prove that the isomorphism ConL[D](ConL)[ConD] holds for a latticeL and a bounded distributive latticeD iff either ConL orD is finite.The research of the first author was supported by the NSERC of Canada.The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

Packing and covering the plane with translates of a convex polygon

A covering of the Euclidean plane by a polygon P is a system of translated copies of P whose union is the plane, and a packing of P in the plane is a system of translated copies of P whose interiors are disjoint. A lattice covering is a covering in which the translates are defined by the points of a lattice, and a lattice packing is defined similarly. We show that, given a convex polygon P with n vertices, the densest lattice packing of P in the plane can be found in O(n) time. We also show that the sparsest lattice covering of the plane by a centrally symmetric convex polygon can be solved in O(n) time. Our approach utilizes results from classical geometry that reduce these packing and covering problems to the problems of finding certain extremal enclosed figures within the polygon.     

The lattice of strict completions of a finite poset

For a given finite poset , we construct strict completions of P which are models of all finite lattices L such that the set of join-irreducible elements of L is isomorphic to P. This family of lattices, , turns out to be itself a lattice, which is lower bounded and lower semimodular. We determine the join-irreducible elements of this lattice. We relate properties of the lattice to properties of our given poset P, and in particular we characterize the posets P for which . Finally we study the case where is distributive. Received October 13, 2000; accepted in final form June 13, 2001.     

The convexity lattice of a poset

The authors investigate the lattice Co(P) of convex subsets of a general partially ordered set P. In particular, they determine the conditions under which Co(P) and Co(Q) are isomorphic; and give necessary and sufficient conditions on a lattice L so that L is isomorphic to Co(P) for some P.     

Sublattices of the Lattices of Strong P-Congruences on P-Inversive Semigroups

In this paper, we describe strong P-congruences and sublattice-structure of the strong P-congruence lattice C_P(S) of a P-inversive semigroup S(P). It is proved that the set of all strong P-congruences C_P(S) on S(P) is a complete lattice. A close link is discovered between the class of P-inversive semigroups and the well-known class of regular ⋆-semigroups. Further, we introduce concepts of strong normal partition/equivalence, C-trace/kernel and discuss some sublattices of C_P(S). It is proved that the set of strong P-congruences, which have C-traces (C-kernels) equal to a given strong normal equivalence of P (C-kernel), is a complete sublattice of C_P(S). It is also proved that the sublattices determined by C-trace-equaling relation θ and C-kernel-equaling relation κ, respectively, are complete sublattices of C_P(S) and the greatest elements of these sublattices are given.     

Notes on Coalition Lattices

Given a finite partially ordered set P, for subsets or, in other words coalitions X, Y of P let X Y mean that there exists an injection : X Y such that x (x) for all x X. The set L(P) of all subsets of P equipped with this relation is a partially ordered set. When L(P) is a lattice, it is called the coalition lattice of P. It is shown that P is determined by the coalition lattice L(P). Further, any coalition lattice satisfies the Jordan–Hölder chain condition. The so-called winning coalitions, i.e. coalitions X such that P\X X in L(P), are shown to form a dual ideal in L(P). Finally, an inductive formula on P is given to describe the lattice operations in L(P), and this result also works for certain quasiordered sets P.     

Going down in (semi)lattices of finite moore families and convex geometries

In this paper we first study what changes occur in the posets of irreducible elements when one goes from an arbitrary Moore family (respectively, a convex geometry) to one of its lower covers in the lattice of all Moore families (respectively, in the semilattice of all convex geometries) defined on a finite set. Then we study the set of all convex geometries which have the same poset of join-irreducible elements. We show that this set—ordered by set inclusion—is a ranked join-semilattice and we characterize its cover relation. We prove that the lattice of all ideals of a given poset P is the only convex geometry having a poset of join-irreducible elements isomorphic to P if and only if the width of P is less than 3. Finally, we give an algorithm for computing all convex geometries having the same poset of join-irreducible elements.      

Lattices compatible with regular polytopes

In a recent paper, Karpenkov has classified the lattice polytopes (that is, with vertices in the integer lattice ) which are regular with respect to those affinities which preserve the lattice. An alternative approach is adopted in this paper. For each regular polytope P in euclidean space , those lattices Λ are classified which are compatible with P, in the sense that some translate of Λ contains the vertices of P, and this translate is preserved by the symmetries of P.     

Lattice polytopes,Hecke operators,and the Ehrhart polynomial

Let P be a simple lattice polytope. We define an action of the Hecke operators on E(P), the Ehrhart polynomial of P, and describe their effect on the coefficients of E(P). We also describe how the Brion–Vergne formula for E(P) transforms under the Hecke operators for nonsingular lattice polytopes P.      

Extending a Partially Ordered Set: Links with its Lattice of Ideals

A well-known result of Bonnet and Pouzet bijectively links the set of linear extensions of a partial order P with the set of maximal chains of its lattice of ideals I(P). We extend this result by showing that there is a one-to-one correspondence between the set of all extensions of P and the set of all sublattices of I(P) which are chain-maximal in the sense that every chain which is maximal (for inclusion) in the sublattice is also maximal in the lattice.We prove that the absence of order S as a convex suborder of P is equivalent to the absence of I(S) as a convex suborder of I(P). Let S be a set of partial orders and let us call S-convex-free any order that does not contain any order of S as a convex suborder. We deduce from the previous results that there is a one-to-one correspondence between the set of S-convex-free extensions of P and the set of I(S)-convex-free chain-maximal sublattices of I(P). This can be applied to some classical classes of orders (total orders and in the finite case, weak orders, interval orders, N-free orders). In the particular case of total orders this gives as a corollary the result of Bonnet and Pouzet.     

Congruences on eventually regular semigroups

Let S be an eventually regular semigroup. The extensively P-partial congruence pairs and P-partial congruence pairs for S are defined. Furthermore, the relationships between the lattice of congruences on S, the lattice of P-partial kernel normal systems for S, the lattice of extensively P-partial kernel normal systems for S and the poset of P-partial congruence pairs for S are explored.     

Chermak–Delgado Lattice Extension Theorems

If G is a finite group with subgroup H, then the Chermak–Delgado measure of H (in G) is defined as |H||C _G (H)|. The Chermak–Delgado lattice of G, denoted 𝒞𝒟(G), is the set of all subgroups with maximal Chermak–Delgado measure; this set is a moduar sublattice within the subgroup lattice of G. In this paper we provide an example of a p-group P, for any prime p, where 𝒞𝒟(P) is lattice isomorphic to 2 copies of ?₂ (a quasiantichain of width 2) that are adjoined maximum-to-minimum. We introduce terminology to describe this structure, called a 2-string of 2-diamonds, and we also give two constructions for generalizing the example. The first generalization results in a p-group with Chermak–Delgado lattice that, for any positive integers n and l, is a 2l-string of n-dimensional cubes adjoined maximum-to-minimum and the second generalization gives a construction for a p-group with Chermak–Delgado lattice that is a 2l-string of ? _p+1 (quasiantichains, each of width p + 1) adjoined maximum-to-minimum.     

Realizable Quadruples for Hex-polygons

There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ² with vertices in the integral lattice ℤ². Geometrically, ℤ² is the set of corners of a tiling of ℝ² by unit squares. Denote by H the set of corners of a tiling of the plane by regular hexagons of unit area and call a polygon P a Hex-polygon or an H-polygon if all vertices of P are in H. Our purpose is to study several combinatorial properties of H-polygons that are analogous to properties of lattice polygons. In particular we aim to find some relationships between the numbers b and i of points from H on the boundary and in the interior of an H-polygon P with the numbers v and c of vertices and the so-called boundary characteristic of P. We also pose three open problems dealing with convex Hex-polygons.     

The quasi-invariance property for the Gamma kernel determinantal measure

The Gamma kernel is a projection kernel of the form (A(x)B(y)−B(x)A(y))/(x−y), where A and B are certain functions on the one-dimensional lattice expressed through Euler's Γ-function. The Gamma kernel depends on two continuous parameters; its principal minors serve as the correlation functions of a determinantal probability measure P defined on the space of infinite point configurations on the lattice. As was shown earlier [A. Borodin, G. Olshanski, Adv. Math. 194 (2005) 141–202, arXiv:math-ph/0305043], P describes the asymptotics of certain ensembles of random partitions in a limit regime.Theorem: The determinantal measure P is quasi-invariant with respect to finitary permutations of the nodes of the lattice.This result is motivated by an application to a model of infinite particle stochastic dynamics.     

The Reflexive Dimension of a Lattice Polytope

The reflexive dimension refldim(P) of a lattice polytope P is the minimal integer d so that P is the face of some d-dimensional reflexive polytope. We show that refldim(P) is finite for every P, and give bounds for refldim(kP) in terms of refldim(P) and k. Received July 2, 2004     

Right angle free subsets in the plane

In this paper we investigate the complexity of finding maximum right angle free subsets of a given set of points in the plane. For a set of rational pointsP in the plane, theright angle number (P) (respectivelyrectilinear right angle number _R (P)) ofP is the cardinality of a maximum subset ofP, no three members of which form a right angle triangle (respectively a right angle triangle with its side or base parallel to thex-axis). It is shown that both parameters areNP-hard to compute. The latter problem is also shown to be equivalent to finding a minimum dominating set in a bipartite graph. This is used to show that there is a polynomial algorithm for computing _R (P) whenP is a horizontally-convex subset of the lattice × (P ishorizontally-convex if for any pair of points inP which lie on a horizontal line, every lattice point between them is also inP). We then show that this algorithm yields a 1/2-approximate algorithm for the right angle number of a convex subregion of the lattice.     

Weakening partial orderings to lattice and semilattice orderings

A partial ordering on a set P can be weakened to an upper or lower semilattice ordering, respectively a lattice ordering, if and only if P is filtered in the appropriate direction(s).This work was done while the author was partly supported by NSF contract DMS 85-02330.     

On Large Lattice Packings of Spheres

The packing density of large lattice packings of spheres in Euclidean E ^d measured by the parametric density depends on the parameter and on the shape of the convex hull P of the sphere centers; in particular on the isoperimetric coefficient of P and on the second term in the Ehrhart polynomial of the lattice polytope P. We show in E ^d , d 2, that flat or spherelike polytopes generate less dense packings, whereas polytopes with suitably chosen large facets generate dense packings. This indicates that large lattice packings in E ³ of high parametric density may be good models for real crystals.     

Prefinitely axiomatizable modal and intermediate logics

A logic Λ bounds a property P if all proper extensions of Λ have P while Λ itself does not. We construct logics bounding finite axiomatizability and logics bounding finite model property in the lattice of intermediate logics and in the lattice of normal extensions of K4.3. MSC: 03B45, 03B55.