共查询到20条相似文献,搜索用时 0 毫秒
1.
A partially ordered set is called acircle containment order provided one can assign to each element of the poset a circle in the plane so thatxy iff the circle assigned tox is contained in the circle assigned toy. It has been conjectured that every finite three-dimensional partially ordered set is a circle containment order. We show that the infinite three dimensional posetZ
3 isnot a circle containment order.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.Research supported in part by National Science Foundation, grant number DMS-8403646. 相似文献
2.
David A. Meyer 《Order》1993,10(3):227-237
The recent work on circle orders generalizes to higher dimensional spheres. As spherical containment is equivalent to causal precedence in Minkowski space, we define the Minkowski dimension of a poset to be the dimension of the minimal Minkowski space into which the poset can be embedded; this isd if the poset can be represented by containment with spheresS
d–2 and of no lower dimension. Comparing this dimension with the standard dimension of partial orders we prove that they are identical in dimension two but not in higher dimensions, while their irreducible configurations are the same in dimensions two and three. Moreover, we show that there are irreducible configurations for arbitrarily large Minkowski dimension, thus providing a lower bound for the Minkowski dimension of partial orders. 相似文献
3.
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. 相似文献
4.
Peter Winkler 《Order》1990,7(4):329-339
A relationship is established between (partially) ordered sets of dimension 2 chosen randomly on a labelled set, chosen randomly by isomorphism type, or generated by pairs of random linear orderings. As a consequence we are able to determine the limiting probability (in each of the above sample spaces) that a two-dimensional order is rigid, is uniquely realizable, or has uniquely orientable comparability graph; all these probabilities lie strictly between 0 and 1. Finally, we show that the number of 2-dimensional (partial) orderings of a labelled n-element set is
.On leave from Emory University, Atlanta, GA. Research at Emory supported by ONR grant N00014 85-K-0769. 相似文献
5.
Klaus Reuter 《Order》1989,6(3):277-293
It is known that for incidence structures
and
, max
, wheref dim stands for Ferrers relation. We shall show that under additional assumptions on
and
, both bounds can be improved. Especially it will be shown that the square of a three-dimensional ordered set is at least four-dimensional. 相似文献
6.
Peter Winkler 《Order》1985,2(2):165-171
Let P
k
(n) be the (partial) order determined by intersecting k random linear orderings of a set of size n; equivalently, let P
k
(n) consist of n points chosen randomly and independently from the unit cube in
k
, with the induced product order. We show for each fixed k>1, that with probability approaching 1 as n, the comparability graph of P
k
(n) is connected and has diameter 3. 相似文献
7.
Given a partially ordered setP=(X, ), a collection of linear extensions {L
1,L
2,...,L
r
} is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL
i
(andy<x in someL
j
). For a positive integerk, we call a multiset {L
1,L
2,...,L
t
} ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL
i
's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research. 相似文献
8.
A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281. 相似文献
9.
Let ={P
1,...,P
m
} be a family of sets. A partial order P(, <) on is naturally defined by the condition P
i
<P
j
iff P
i
is contained in P
j
. When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977. 相似文献
10.
A finite poset P(X,<) on a set X={
x
1,...,x
m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x
ij if and only if the angular region (regular n-gon) for x
i is contained in the region (regular n-gon) for x
j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415. 相似文献
11.
This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices. 相似文献
12.
We establish some inequalities connecting natural parameters of a partial order P. For example, if every interval [a,b] contains at most maximal chains, if some antichain has cardinality v, and if there are 1 chains whose union is cofinal and coinitial in P, then the chain decomposition number for P is 1v (Theorem 2.2), and the inequality is sharp in a certain sense (Section 3).This paper was written while the authors were visitors at the Laboratoire d'algèbre ordinale, Département de Mathématiques, Université Claude Bernard, Lyon 1, France.Research supported by NSERC grant # A5198. 相似文献
13.
The purpose of this paper is to give an effective characterization of all interval orders which are greedy with respect to the jump number problem.This research (Math/1406/30) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia. 相似文献
14.
Given a finite collection of disjoint, convex figures on the plane, is it possible to assign to each a single direction of motion so that this collection of figures may be separated, through an arbitrary large distance, by translating each figure one at a time, along its assigned direction? We present a computational model for this separability problem based on the theory of ordered sets. 相似文献
15.
Dorothea Wagner 《Order》1990,6(4):335-350
A decomposition theory for partial orders which arises from the split decomposition of submodular functions is introduced. As a consequence of this theory, any partial order has a unique decomposition consisting of indecomposable partial orders and certain highly decomposable partial orders. The highly decomposable partial orders are completely characterized. As a special case of partial orders, we consider lattices and distributive lattices. It occurs, that the highly decomposable distributive lattices are precisely the Boolean lattices. 相似文献
16.
Some orders can be represented by translating convex figures in the plane. It is proved thatN-free and interval orders admit such representations with an unbounded number of directions. Weak orders, tree-like orders and two-dimensional orders of height one are shown to be two- directional. In all cases line segments can be used as convex sets. 相似文献
17.
Edward R. Scheinerman 《Order》1992,9(4):343-348
A finite partially ordered set P is called a circle order if one can assign to each x P a circular disk C
x
so that xy iff C
x
C
y
. It is interesting to observe that many other classes of posets, such as space-time orders, parabola orders, the Loewner order for 2×2 Hermitian matrices, etc. turn out to be exactly circle orders (or their higher dimensional analogues). We give a global proof for these equivalences.Research supported in part by the Office of Naval Research, the Air Force Office of Scientific Research and by DIMACS. 相似文献
18.
Given a poset (A, r) and an acyclic r-monotone function f: AA, we prove that r can be extended to a linear order R with xRyf(x)Rf(y) for all x, yA. 相似文献
19.
Stefan Felsner 《Order》1990,6(4):325-334
The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number problem is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number.The complexity status for interval orders still remains unknown. Here we present a heuristic that, given an interval order P, generates a linear extension , whose jump number is less than 3/2 times the jump number of P.This work was supported by the Deutsche Forschungsgemeinschaft (DFG). 相似文献