共查询到20条相似文献,搜索用时 31 毫秒
1.
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). 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
In this paper, we describe strong P-congruences and sublattice-structure of the strong P-congruence lattice CP(S) of a P-inversive semigroup S(P). It is proved that the set of all strong P-congruences CP(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 CP(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 CP(S). It is also proved that the sublattices determined by C-trace-equaling relation θ and C-kernel-equaling relation κ, respectively,
are complete sublattices of CP(S) and the greatest elements of these sublattices are given. 相似文献
7.
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. 相似文献
8.
Bordalo Gabriela Caspard Nathalie Monjardet Bernard 《Czechoslovak Mathematical Journal》2009,59(1):249-271
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.
相似文献
9.
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. 相似文献
10.
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.
相似文献
11.
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. 相似文献
12.
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. 相似文献
13.
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 ?2 (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. 相似文献
14.
Krzysztof Kołodziejczyk 《Graphs and Combinatorics》2007,23(1):61-72
There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ2 with vertices in the integral lattice ℤ2. Geometrically, ℤ2 is the set of corners of a tiling of ℝ2 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. 相似文献
15.
Grigori Olshanski 《Advances in Mathematics》2011,(3):2305
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. 相似文献
16.
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 相似文献
17.
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. 相似文献
18.
George M. Bergman 《Order》1986,3(3):283-286
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. 相似文献
19.
J. M. Wills 《Geometriae Dedicata》1997,65(1):117-126
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
3 of high parametric density may be good models for real crystals. 相似文献
20.
N. V. Subrahmanyam 《Mathematische Annalen》1960,139(4):275-286
Conclusion We observe that every Boolean ring is aP
1-ring, where each element is its own minimal idempotent duplicator; a Boolean ring with unity is also aP
2-ring, where each element is the maximal idempotent annihilator of its complement; and thus,P
1-rings andP
2-rings are generalisations of a Boolean ring in terms of its lattice structure. Then, it is only natural that these two classes of rings have such close affiliations with the lattice structure of a Boolean ring. 相似文献