ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (42)
  • 06A06  (42)
  • 2020-2023
  • 1990-1994  (42)
  • Mathematics  (42)
  • Energy, Environment Protection, Nuclear Power Engineering
Collection
  • Articles  (42)
Source
Keywords
Publisher
Years
Year
Topic
  • Mathematics  (42)
  • Energy, Environment Protection, Nuclear Power Engineering
  • 1
    Electronic Resource
    Electronic Resource
    Deciding Frattini is NP-complete (1994)
    Springer
    Order 11 (1994), S. 257-279 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 06D05 ; 68Q15 ; Partially ordered set ; Frattini sublattice ; NP-complete
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show that it is a NP-complete problem to decide whether a finite poset arises as the (Birkhoff) dual of the Frattini sublattice of some finite distributive lattice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02115815
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Fixed points and products (1994)
    Springer
    Order 11 (1994), S. 11-14 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Fixed point property ; retract ; product
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We prove that if the finite ordered setsP andX have the fixed point property then so too doesP×X.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01462225
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Treewidth of cocomparability graphs and a new order-theoretic parameter (1994)
    Springer
    Order 11 (1994), S. 47-60 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Treewidth ; pathwidth ; dimension ; interval dimension ; cocomparability graphs ; approximation algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01462229
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Series-parallel posets and relative Ockham lattices (1994)
    Springer
    Order 11 (1994), S. 281-305 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 06D05 ; Series-parallel poset ; order-reversing map ; distributive lattice ; Ockham algebra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A study is undertaken of order-reversing maps on series-parallel posets and structural characterisations are obtained of various subclasses of such ordered sets. The results are applied to complete the authors' earlier investigation of classes $$\mathcal{A}^{rel} $$ of finite relate $$\mathcal{A}$$ lattices, where $$\mathcal{A}$$ is a variety of Ockham lattices and the distributive lattice duals of the algebras in $$\mathcal{A}^{rel} $$ are required to be series-parallel.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02115816
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Retractability and the fixed point property for products (1994)
    Springer
    Order 11 (1994), S. 353-359 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Fixed point property ; retractable element ; contractible element ; product ; chain completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract LetP, Q be ordered sets and leta∈P. IfP \ {a} is a retract ofP and setsP and {x∈P:x〉p} (or its dual) have the fixed point property then, for each chain complete setP,P×Q has the fixed point property if and only if (P\{a})×Q has this property. This establishes the fixed point property for some products of ordered sets which are beyond the reach of all known product theorems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108767
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    The crossing number of posets (1994)
    Springer
    Order 11 (1994), S. 169-193 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Poset ; crossing number ; product ; lexicographical sum ; Boolean lattice
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The purpose of this paper is to investigate some properties of the crossing number χ(P) of a posetP. We first study the crossing numbers of the product and the lexicographical sum of posets. The results are similar to the dimensions of these posets. Then we consider the problem of what happens to the crossing number when a point is taken away from a poset. We show that ifP is a poset such that χ∈P and χ(P−χ)⩾1, then 1/2 χ(P)⩽χ(P−χ)⩽χ(P). We don't know yet how to improve the lower bound. We also determine the crossing numbers of some subposets of the Boolean latticeB n which consist of some specified ranks. Finally we show that Ψ n is crossing critical where Ψ n is the subposet ofB n which is restricted to rank 1, rankn−1 and middle rank(s). Some open problems are raised at the end of this paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108601
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Cores and retracts (1994)
    Springer
    Order 11 (1994), S. 1-9 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Ordered set ; retract ; core
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Theretracts (idempotent, isotone self-maps) of an ordered set are naturally ordered as functions. In this note we characterize the possible ways that one retract can cover another one. This gives some insight into the structure of the ordered set of retracts and leads to a natural generalization of the core of an ordered set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01462224
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Every triangle-free planar graph has a planar upward drawing (1993)
    Springer
    Order 10 (1993), S. 1-16 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Planar graph ; triangle-free ; upward drawing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A planar ordered set has a triangle-free, planar covering graph; on the other hand, there are nonplanar ordered sets whose covering graphs are planar. We show thatevery triangle-free planar graph has a planar upward drawing. This planar upward drawing can be constructed in time, polynomial in the number of vertices. Our results shed light on the apparently difficult problem, of long-standing, whether there is aneffective planarity-testing procedure for an ordered set.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108704
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On the dimension of ordered sets with the 2-cutset property (1993)
    Springer
    Order 10 (1993), S. 37-54 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Ordered set ; cutset ; 2-cutset property ; chain ; antichain ; width ; linear extension ; dimension
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An ordered setP is said to have 2-cutset property if, for every elementx ofP, there is a setS of elements ofP which are noncomparable tox, with |S|⩽2, such that every maximal chain inP meets {x}∪S. We consider the following question: Does there exist ordered sets with the 2-cutset property which have arbitrarily large dimension? We answer the question in the negative by establishing the following two results.Theorem: There are positive integersc andd such that every ordered setP with the 2-cutset property can be represented asP=X∪Y, whereX is an ordinal sum of intervals ofP having dimension ⩽d, andY is a subset ofP having width ⩽c. Corollary: There is a positive integern such that every ordered set with the 2-cutset property has dimension ⩽n.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108707
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Spherical containment and the Minkowski dimension of partial orders (1993)
    Springer
    Order 10 (1993), S. 227-237 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 52A37 ; Causal order ; spherical (containment) order ; Minkowski dimension
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01110544
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Transforming binary sequences using priority queues (1993)
    Springer
    Order 10 (1993), S. 31-36 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Priority queue ; binary sequence ; enumeration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A priority queue transforms an input sequence σ into an output sequence τ which is a re-ordering of the sequence σ. The setR of all such related pairs is studied in the case that σ is a binary sequence. It is proved thatR is a partial order and that ¦R¦=c n+1, the (n+1)th Catalan number. An efficient (O(n 2)) algorithm is given for computing the number of outputs achievable from a given input.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A chain complete poset with no infinite antichain has a finite core (1993)
    Springer
    Order 10 (1993), S. 55-63 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Poset ; PT-order ; chain complete ; retract ; fixed-point ; core
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract It is well known that dismantling a finite posetP leads to a retract, called the core ofP, which has the fixed-point property if and only ifP itself has this property. The PT-order, or passing through order, of a posetP is the quasi order ⊴ defined onP so thata⊴b holds if and only if every maximal chain ofP which passes througha also passes throughb. This leads to a generalization of the dismantling procedure which works for arbitrary chain complete posets which have no infinite antichain. We prove that such a poset also has a finite core, i.e. a finite retract which reflects the fixed-point property forP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108708
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Gray codes from antimatroids (1993)
    Springer
    Order 10 (1993), S. 239-252 
    Details
    ISSN: 1572-9273
    Keywords: 05C45 ; 06A05 ; 06A06 ; Antimatroid ; basic word graph ; combinatorial Gray code ; Hamiltonicity ; join-distributive lattice
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids. For antimatroid (E, $$\mathcal{F}$$ ), letJ( $$\mathcal{F}$$ ) denote the graph whose vertices are the sets of $$\mathcal{F}$$ , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( $$\mathcal{F}$$ ;k) to be the subgraph ofJ( $$\mathcal{F}$$ )2 induced by the sets in $$\mathcal{F}$$ with exactlyk elements. Both graphsJ( $$\mathcal{F}$$ ) andJ( $$\mathcal{F}$$ ;k) are connected, and the former is bipartite. We show that there is a Hamiltonian cycle inJ( $$\mathcal{F}$$ )×K 2. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( $$\mathcal{F}$$ ;k) has a Hamilton path if (E, $$\mathcal{F}$$ ) is the poset antimatroid of a series-parallel poset. Similarly, we show thatG( $$\mathcal{L}$$ )×K 2 is Hamiltonian, whereG( $$\mathcal{L}$$ ) is the “basic word graph” of a language antimatroid (E, $$\mathcal{L}$$ ). This result was known previously for poset antimatroids.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01110545
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Fixed point property for 11-element sets (1993)
    Springer
    Order 10 (1993), S. 329-347 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Fixed point property ; irreducible point ; dismantable poset ; retractable point
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We introduce retractable points and show how this notion provides the key for a classification of all sets with 11 elements that have the fixed point property.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    On trees and tree dimension of ordered sets (1993)
    Springer
    Order 10 (1993), S. 153-160 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Tree ; dimension
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We call an ordered set (X, ⩽) a tree if no pair of incomparable elements ofX has an upper bound. It is shown that there is a natural way to associate a tree (T, ⩽) with any ordered set (X, ⩽), and (T, ⩽) can be characterized by a universal property. We define the tree dimensiontd(X, ⩽) of an ordered set as the minimal number of extensions of (X, ⩽) which are trees such that the given order is the intersection of those tree orders. We give characterizations of the tree dimension, relations between dimension and tree dimension, and removal theorems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01111300
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    A note on sphere containment orders (1993)
    Springer
    Order 10 (1993), S. 143-145 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Sphere containment order ; circle containment order
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Using the ideas of Scheinerman and Wierman [1] and of Hurlbert [2] we give a very short proof that the infinite order [2]×[3]×ω cannot be represented by containment of Euclidean balls in ad-dimensional space for anyd. Also we give representations of the orders [2]×[2]×ω and [3]×[3]×[3] by containment of circles in the plane.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01111298
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    The dimension of orthomodular posets constructed by pasting Boolean algebras (1993)
    Springer
    Order 10 (1993), S. 183-197 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 06A07 ; Dimension ; Boolean algebra ; atomic amalgam
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The main aim of this paper is the calculation of the dimension of certain atomic amalgams. These consist of finite Boolean algebras (blocks) pasted together in such a way that a pair of blocks intersects either trivially in the bounds, or the intersection consists of the bounds, an atom, and its complement.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01111302
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    On the complexity of diagram testing (1993)
    Springer
    Order 10 (1993), S. 297-303 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 68Q25 ; Diagram ; orientation ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In 1987, Nešetřil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Nešetřil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108825
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    The core of a chain complete poset with no one-way infinite fence and no tower (1993)
    Springer
    Order 10 (1993), S. 349-361 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Chain complete poset ; fixed point property ; perfect sequence ; core
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Like dismantling for finite posets, a perfect sequence Π = 〈P ξ :ξ≤λ〉 of a chain complete posetP represents a canonical procedure to produce a coreP λ. It has been proved that if the posetP contains no infinite antichain then this coreP λ is a retract ofP andP has the fixed point property iffP λ has this property. In this paper the condition of having no infinite antichain is replaced by a weaker one. We show that the same conclusion holds under the assumption thatP does not contain a one-way infinite fence or a tower.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01108829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    Greene-Kleitman's theorem for infinite posets (1992)
    Springer
    Order 9 (1992), S. 245-253 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Posets ; chains ; antichains ; matchings ; covers
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract It is proved that if (P⩽) is a poset with no infinite chain and k is a positive integer, then there exist a partition of P into disjoint chains C i and disjoint antichains A 1, A 2, ..., A k, such that each chain C i meets min (k, |C i|) antichains A j. We make a ‘dual’ conjecture, for which the case k=1 is: if (P⩽) is a poset with no infinite antichain, then there exist a partition of P into antichains A i and a chain C meeting all A i. This conjecture is proved when the maximal size of an antichain in P is 2.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383948
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    On the strong fixed point property (1992)
    Springer
    Order 9 (1992), S. 305-310 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Fixed point property ; strong fixed point property
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An ordered set which has the fixed point property but not the strong fixed point property is presented
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00420349
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Enumeration of order preserving maps (1992)
    Springer
    Order 9 (1992), S. 15-29 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; (Partially) ordered set ; order preserving map ; enumeration ; stochastic process ; martingale
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Three results are obtained concerning the number of order preserving maps of an n-element partially ordered set to itself. We show that any such ordered set has at least 2 2n/3 order preserving maps (and 2 2 in the case of length one). Precise asymptotic estimates for the numbers of self-maps of crowns and fences are also obtained. In addition, lower bounds for many other infinite families are found and several precise problems are formulated.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00419036
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Two properties of projective orders (1992)
    Springer
    Order 9 (1992), S. 233-238 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 08A40 ; Order ; projective ; ramified ; monotone idempotent operation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We prove a closure property of the class of projective orders without infinite chains, and strengthen Larose's theorem on the equivalence between projectivity and quasiprojectivity for finite orders.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383946
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Order-discriminating operations (1992)
    Springer
    Order 9 (1992), S. 239-244 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 08A40 ; Ternary discriminator ; dual discriminator ; near-projection ; bounded partial order ; functionally complete ; Rosenberg's completeness theorem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Algebras with an operator that discriminates order are functionally complete.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383947
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    N-free orders and minimal interval extensions (1992)
    Springer
    Order 9 (1992), S. 291-302 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Partial orders ; algorithms ; N-free orders ; interval orders
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We investigate problems related to the set of minimal interval extensions of N-free orders. This leads us to a correspondence between this set for an arbitrary order and a certain set of its maximal N-free reductions. We also get a 1-1-correspondence between the set of linear extensions of an arbitrary order and the set of minimal interval extensions of the linegraph of that order. This has an algorithmic consequence, namely the problem of counting minimal interval extensions of an N-free order is #P-complete. Finally a characterization of all N-free orders with isomorphic root graph is given in terms of their lattice of maximal antichains; the lattices are isomorphic iff the root graphs agree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383951
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    Finding the largest suborder of fixed width (1992)
    Springer
    Order 9 (1992), S. 357-360 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 68M20 ; Ordered sets ; width ; maximum suborder
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Finding the largest suborder of fixed width in a partially ordered set is an interesting combinatorial problem with applications in combinatorial optimization and scheduling. We present a polynomial time solution for this problem by transforming it into a minimum cost network flow problem in an appropriate auxiliary network.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00420355
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Fractional dimension of partial orders (1992)
    Springer
    Order 9 (1992), S. 139-158 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Dimension ; fractional dimension
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00814406
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    The strong fixed point property for lexicographic sums (1992)
    Springer
    Order 9 (1992), S. 311-319 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; (Strong) fixed point property ; lexicographic sum
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The following theorem is proved: If Q=L{P t ∣t∈T} is a finite lexicographic sum of posets such that T and all P t have the strong fixed point property then Q has the strong fixed point property. Moreover we show the strong fixed point property for two more classes of posets.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00420350
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Drawing orders using less ink (1992)
    Springer
    Order 9 (1992), S. 5-13 
    Details
    ISSN: 1572-9273
    Keywords: 06-04 ; 06A06 ; 90C35 ; Diagram ; partially ordered set ; algorithm ; iteration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An algorithm is presented to draw Hasse-diagrams of partially ordered sets (orders). It uses two heuristic principles to generate ‘good’ pictures for a wide range of orders. These two principles are (i) The total length of all edges of the diagram should be small (with the vertices kept at a minimal distance) and (ii) the vertices are constrained to coincide with the grid points of a given rectangular planar grid. The benefits are quite straightforward sine (i) using less ink means less confusion and (ii) the restriction to grid points tends to keep the number of different slopes small. Since the program was conceived as a readily usable tool (with the emphasis on results rather than on perfection), we are well aware of the fact that it will lend itself easily to improvements in many aspects.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00419035
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    The PT-order and the fixed point property (1992)
    Springer
    Order 9 (1992), S. 321-331 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; (Partially) ordered set ; PT-order ; chain complete ; retract ; fixed-point property
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The PT-order, or passing through order, of a poset P is a quasi order ⊴ defined on P so that a⊴b holds if and only if every maximal chain of P which passes throug a also passes through b. We show that if P is chain complete, then it contains a subset X which has the properties that (i) each element of X is ⊴-maximal, (ii) X is a ⊴-antichain, and (iii) X is ⊴-dominating; we call such a subset a ⊴-good subset of P. A ⊴-good subset is a retract of P and any two ⊴-good subsets are order isomorphic. It is also shown that if P is chain complete, then it has the fixed point property if and only if a ⊴-good subset also has the fixed point property. Since a retract of a chain complete poset is also chain complete, the construction may be iterated transfinitely. This leads to the notion of the “core” of P (a ⊴-good subset of itself) which is the transfinite analogue of the core of a finite poset obtained by dismantling.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00420351
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Order, genus, and diagram invariance (1991)
    Springer
    Order 8 (1991), S. 107-113 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Order ; genus ; invariance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The genus of any ordered set equals the genus of its covering graph, and, therefore, the genus of an ordered set is a diagram invariant.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383397
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    The strong fixed point property for small sets (1991)
    Springer
    Order 8 (1991), S. 29-32 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; (strong) fixed point property
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract It is shown that every partially ordered set with the fixed point property and with ten or fewer elements actually has the strong fixed point property.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00385811
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Order varieties generated by finite posets (1991)
    Springer
    Order 8 (1991), S. 341-348 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Colored posets ; zigzags ; order varieties ; irreducible posets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In a 1981 paper, Duffus and Rival define an order variety as a class of posets that is closed under the formation of products and retracts. They also introduce the notion of an irreducible poset. In the present paper we define nonextendible colored posets and certain minimal nonextendible colored posets that we call zigzags. We characterize via nonextendible colored posets the order varieties generated by a set of posets. If the generating set contains only finite posets our characterization is via zigzags. By using these theorems we give a characterization of finite irreducible posets. As an application we show that two different finite irreducible posets generate two different order varieties. We also show that there is a poset which has two different representations by irreducible posets. We thereby settle two open problems listed in the Duffus and Rival paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00571184
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Multiplicative posets (1991)
    Springer
    Order 8 (1991), S. 349-358 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Posets ; strict morphisms ; multiplicativity ; Hedetniemi's conjecture
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A functionf from the posetP to the posetQ is a strict morphism if for allx, y ∈ P withx〈y we havef(x)〈f(y). If there is such a strict morphism fromP toQ we writeP → Q, otherwise we writeP $$\not \to $$ Q. We say a posetM is multiplicative if for any posetsP, Q withP $$\not \to $$ M andQ $$\not \to $$ M we haveP ×Q $$\not \to $$ M. (Here (p 1,q 1)〈(p 2,q 2) if and only ifp 1〈p 2 andq 1〈q 2.) This paper proves that well-founded trees with height ≤ω are multiplicative posets.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00571185
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Counting finite posets and topologies (1991)
    Springer
    Order 8 (1991), S. 247-265 
    Details
    ISSN: 1572-9273
    Keywords: 05A15 ; 05A19 ; 06A06 ; 54-04 ; Quasiordered set ; partially ordered set ; topology ; connected ; separation axiom ; antichain ; generating function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n≤11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n≤14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n≤11 and all k, and then the numbers of all topologies on n≤14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 1023.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383446
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    On the conductance of order Markov chains (1991)
    Springer
    Order 8 (1991), S. 7-15 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Conductance ; isoperimetric inequality ; linear extension ; poset ; uniform generation ; sorting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Let Q be a convex solid in ℝ n , partitioned into two volumes u and v by an area s. We show that s〉min(u,v)/diam Q, and use this inequality to obtain the lower bound n -5/2 on the conductance of order Markov chains, which describe nearly uniform generators of linear extensions for posets of size n. We also discuss an application of the above results to the problem of sorting of posets.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00385809
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Chromatic number of Hasse diagrams, eyebrows and dimension (1991)
    Springer
    Order 8 (1991), S. 41-48 
    Details
    ISSN: 1572-9273
    Keywords: 05C15 ; 05C20 ; 06A06 ; Chromatic number ; partially ordered sets ; dimension ; Hasse diagrams
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We construct posets of dimension 2 with highly chromatic Hasse diagrams. This solves a previous problem by Nesetril and Trotter.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00385813
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    [2] x [3] x N is not a circle order (1991)
    Springer
    Order 8 (1991), S. 243-246 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Poset ; circle order ; dimension
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The result stated in the title is proved in this note. Actually we show that S x N is not a circle order, where S={(1, 1), (1, 2), (1, 3), (2, 1), (2, 3)}. Furthermore this non-circle order is critical in the sense that (S-{x}) x N is a circle order for any x in S.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383445
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Finite projective ordered sets (1991)
    Springer
    Order 8 (1991), S. 33-40 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 08A40 ; Isotone operation ; ordered set ; projective ; ramified
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We show that quasiprojectivity and projectivity are equivalent properties for finite ordered sets of more than two elements.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00385812
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Transitive closure for restricted classes of partial orders (1991)
    Springer
    Order 8 (1991), S. 175-183 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 68Q25 ; 05C85 ; Transitive closure ; N-free partial order ; two dimensional partial order
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383402
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Counting linear extensions (1991)
    Springer
    Order 8 (1991), S. 225-242 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; 68C25 ; Partial order ; linear extension ; #P-complete
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We survey the problem of counting the number of linear extensions of a partially ordered set. We show that this problem is #P-complete, settling a long-standing open question. This result is contrasted with recent work giving randomized polynomial-time algorithms for estimating the number of linear extensions. One consequence of our main result is that computing the volume of a rational polyhedron is strongly #P-hard. We also show that the closely related problems of determining the average height of an element x of a give poset, and of determining the probability that x lies below y in a random linear extension, are #P-complete.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00383444
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    On the number of nondismantlable posets with the fixed point property (1991)
    Springer
    Order 8 (1991), S. 325-329 
    Details
    ISSN: 1572-9273
    Keywords: 06A06 ; Fixed point property ; product ; dismantlable poset ; irreducible point
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We give a lower bound for the number of orders on a finite set that are not dismantlable and have the fixed point property. To do so we also derive an upper bound for the number of orders on a finite set that are dismantlable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00571182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...