ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • Artikel  (150)
  • Weitere Quellen
  • 06A10  (88)
  • diffusion  (62)
  • Springer  (150)
  • 2015-2019
  • 1995-1999  (56)
  • 1985-1989  (93)
  • 1970-1974  (1)
  • Mathematik  (98)
  • Maschinenbau  (43)
  • Technik allgemein  (14)
Sammlung
  • Artikel  (150)
  • Weitere Quellen
Verlag/Herausgeber
Erscheinungszeitraum
Jahr
  • 1
    Digitale Medien
    Digitale Medien
    Springer
    Colloid & polymer science 265 (1987), S. 810-814 
    ISSN: 1435-1536
    Schlagwort(e): Crystal growth ; syndiotactic poly(vinyl alcohol) ; hydrogels ; Liesegang rings ; diffusion
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Maschinenbau
    Notizen: Abstract Aqueous solutions of syndiotacticity-rich poly(vinyl alcohol) (s-PVA) form gels easily. The optimum condition of growth of the calcium tartrate crystal formed by diffusing calcium chloride into hydrogels containing tartaric acid was studied with use ofs- PVA of a syndiotacticity of 56 % and a degree of polymerization of 1460. The crystal grew in the gel of the concentrations of 2 % s-PVA and of 0.5 N tartaric acid at pH=4. The relation between the formation of Liesegang rings and shear modulus of a gel was studied by diffusing silver nitrate into gels containing potassium chromate. The distance between rings decreased with increasing shear modulus of a gel in the range from 670 to 7500 dyne/cm2. The Liesegang rings were not formed for the shear modulus gel for 280 and 16200 dyne/cm2.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 2
    ISSN: 1435-1536
    Schlagwort(e): Microemulsions ; diffusion ; NMR ; QELS
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Maschinenbau
    Notizen: Abstract Diffusion studies were performed with various methods to obtain some insight into the structure and the dynamical processes of three and four component microemulsions containing p-nonylphenol ethylene oxide adducts which were mixtures of highly branched p-nonyl isomers with well defined distributions of the ethylene oxide chain length. Diffusion coefficients were determined by pulsed field gradient and pulsed field gradient Fourier transform1 H NMR as well as by quasi-elastic light scattering. The combined application of pulsed field gradient NMR and quasi-elastic light scattering gives information about the critical behaviour of the systems whereas pulsed field gradient Fourier transform NMR allows the determination of the diffusion coefficients of the individual constituents. The results suggest that the very complex three and four component microemulsions studied undergo critical concentration fluctuations in a large temperature region from about 15 °C below the lower critical solution temperatures. The deduced critical exponents are in good agreement with theoretical predictions. The aggregates in the three and four component microemulsions show differences in the self diffusion behaviour of their constituents.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 3
    Digitale Medien
    Digitale Medien
    Springer
    Colloid & polymer science 104 (1997), S. 49-58 
    ISSN: 1435-1536
    Schlagwort(e): Single-mode dynamic light scattering ; opaque porous media ; diffusion ; convection ; tortuosity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Maschinenbau
    Notizen: Abstract Single-mode fiber optical receivers have become the instrumentation standard for Dynamic Light Scattering (DLS). In a regular homodyne experiment one values their superb signal-to-noise ratio as well as the simplicity of the optical setup. Moreover, mode-selective DLS enables the researcher to tackle seemingly hopeless experimental problems, such as colloidal motions inside an opaque porous medium consisting of a water filled packing of small glass grains. The particles to be measured are completely masked by strong diffuse scattering in the porous matrix. Nevertheless, mode-selective DLS makes it possible not only to detect the motions of the colloids within the pores but also to determine their diffusion coefficient and, simultaneously, their average convective speed. We outline the theoretical background of these measurements and present data on diffusion and convection of latex particles in dense packings of glass-beads in a Chromatographic column. Our technique allows an accurate determination of the tortuosity of the interstitial flow.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 4
    Digitale Medien
    Digitale Medien
    Springer
    Journal of polymers and the environment 7 (1999), S. 35-40 
    ISSN: 1572-8900
    Schlagwort(e): Starch ; starch blends ; sorption ; diffusion ; biodegradation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Energietechnik , Maschinenbau
    Notizen: Abstract The interval sorption and diffusion of water vapor were studied for two systems: methylcellulose (MC)/starch and carboxymethylcellulose (CMC)/starch. The diffusion coefficient of water vapor and the Gibbs free energy of swelling of these blends in water were estimated. The Gibbs free energy of mixing starch with the cellulose derivatives was determined using the thermodynamic cycle. CMC/starch was shown to be more compatible than MC/starch. Biodegradation of these systems in the water–soil environment was measured and found to increase with the concentration of starch in its blends with cellulose derivatives.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 5
    Digitale Medien
    Digitale Medien
    Springer
    Order 12 (1995), S. 213-220 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Parallel computation ; m-machine problem ; tree
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract LetP={v 1,...,v n } be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv i has to be executed before the jobv j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay. In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 6
    Digitale Medien
    Digitale Medien
    Springer
    Order 12 (1995), S. 327-349 
    ISSN: 1572-9273
    Schlagwort(e): 06A07 ; 06A10 ; Partially ordered set ; linear extension ; balancing pairs ; cross-product conjecture ; Ahlswede-Daykin inequality ; sorting
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In a finite partially ordered set, Prob (x〉y) denotes the proportion of linear extensions in which elementx appears above elementy. In 1969, S. S. Kislitsyn conjectured that in every finite poset which is not a chain, there exists a pair (x,y) for which 1/3⩽Prob(x〉y)⩽2/3. In 1984, J. Kahn and M. Saks showed that there exists a pair (x,y) with 3/11〈Prob(x〉y)〈8/11, but the full 1/3–2/3 conjecture remains open and has been listed among ORDER's featured unsolved problems for more than 10 years. In this paper, we show that there exists a pair (x,y) for which (5−√5)/10⩽Prob(x〉y)⩽(5+√5)/10. The proof depends on an application of the Ahlswede-Daykin inequality to prove a special case of a conjecture which we call the Cross Product Conjecture. Our proof also requires the full force of the Kahn-Saks approach — in particular, it requires the Alexandrov-Fenchel inequalities for mixed volumes. We extend our result on balancing pairs to a class of countably infinite partially ordered sets where the 1/3–2/3 conjecture isfalse, and our bound is best possible. Finally, we obtain improved bounds for the time required to sort using comparisons in the presence of partial information.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 7
    Digitale Medien
    Digitale Medien
    Springer
    Order 13 (1996), S. 101-117 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; (Partially) ordered set ; maximal chain ; maximal antichain ; cutset ; fibre
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract There is a product of two linear orders of size $$2^{\aleph _0 } $$ with the property that every subset or complement thereof contains a maximal chain. Furthermore, for regular ℵα, there is a product of two linear orders of size ℵα+2 that when colored with fewer than ℵα colors always has a monochromatic maximal chain. As a corollary, for every uncountable strong limit cardinal κ, there is an ordered set of cardinality κ that must be colored with at least κ colors before no monochromatic maximal chains are present. Duals of these results show that at least as much is true for maximal antichains.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 8
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 193-198 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06D99 ; 52A25 ; Finite distributive lattices ; finite posets ; valuations ; convex polytopes ; extreme points
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Let L be a finite distributive lattice and V(L) the real vector space of all valuations on L. We verify the conjecture of Geissinger that the extreme points of the convex polytope M(L)={v ∈ L : 0 ≤ v ≤ 1} are precisely the 0–1 valuations.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 9
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 257-264 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68E05 ; Sorting ; merging ; linear extension
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract For a finite poset P and x, yεP let pr(x〉y) be the fraction of linear extensions which put x above y. N. Linial has shown that for posets of width 2 there is always a pair x, y with 1/3 ⩽ pr(x〉y)⩽2/3. The disjoint union C 1∪C 2 of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In this paper the extreme case is characterized: If P is a poset of width 2 then the bound 1/3 is exact iff P is an ordinal sum of C 1∪C 2's and C 1's.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 10
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 283-286 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06A12 ; 06B99 ; Partially ordered set ; semilattice ; lattice ; cofinality
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract 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).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 11
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1987), S. 355-357 
    ISSN: 1572-9273
    Schlagwort(e): 05App ; 06A10 ; Factor poset ; antichain ; depth
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Denote g(m, n) the minimum of min A, where A is a subset of {1, 2, ..., m} of size n and there do not exist two distinct x and y in A such that x divides y. We use a method of poset to prove that g(m, n)=2 i for positive integer i≤log3 m and 1+s(m, i−1)〈n≤1+s(m, i), where s(m, i) is the number of odd integers x such that m/3 i 〈x≤m.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 12
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 127-142 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68-XX ; Poset ; closures ; Hasse diagram
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The combinatorial properties of the poset of closures are studied, especially the degrees in the Hasse diagram.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 13
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 1-2 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Jump number
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The following result is proved in this note: For any positive integers w and t, if an ordered set P has jump number at least (t+1) w−1, then either the width of P is more than w, or P has a tower, i.e., a linear sum of pairs of noncomparable elements, of height more than t.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 14
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 155-164 
    ISSN: 1572-9273
    Schlagwort(e): 05C55 ; 06A10 ; 62J ; Regressions ; Ramsey theory
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A regressive function (also called a regression or contractive mapping) on a partial order P is a function σ mapping P to itself such that σ(x)≤x. A monotone k-chain for σ is a k-chain on which σ is order-preserving; i.e., a chain x 1〈...〈xksuch that σ(x 1)≤...≤σ(xk). Let P nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x t(x,j−1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) 〈 f(K) 〈t(е + εk, k) , where εk → 0 as k→∞. Alternatively, the largest k such that every regression on P nis guaranteed to have a monotone k-chain lies between lg*(n) and lg*(n)−2, inclusive, where lg*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 15
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 269-272 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 05A15 ; Interval order ; enumeration
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An algorithm is obtained for enumerating the interval orders of a given cardinality.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 16
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1987), S. 345-353 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06A23 ; Order-dimension ; Ferrers relation ; partition lattice ; linear lattice
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The aim of this paper is to study the order-dimension of partition lattices and linear lattices. Our investigations were motivated by a question due to Bill Sands: For a lattice L, does dim L=n always imply |L|≥2 n ? We will answer this question in the negative since both classes of lattices mentioned above form counterexamples. In the case of the partition lattices, we will determine the dimension up to an absolute constant. For the linear lattice over GF(2), L n , we determine the dimension up to a factor C/n for an absolute constant C.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 17
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1987), S. 369-382 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partial order ; tree ; chain decomposition ; width
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract 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 ⩽χ1λv (Theorem 2.2), and the inequality is sharp in a certain sense (Section 3).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 18
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 37-42 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partially ordered sets ; Van der Waerden's arithmetic sequence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Van der Waerden's arithmetic sequence theorem—in particular, the ‘density version’ of Szemerédi—is generalized to partially ordered sets in the following manner. Let w and t be fixed positive integers and ε〉0. Then for every sufficiently large partially ordered set P of width at most w, every subset S of P satisfying |S|≥ε|P| contains a chain a 1, a 2,..., a 1 such that the cardinality of the interval [a i, a i+1] in P is the same for each i.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 19
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 163-171 
    ISSN: 1572-9273
    Schlagwort(e): 05C45 ; 05C70 ; 06A10 ; Boolean lattice ; Hamiltonian cycle ; matching
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract New classes of explicit matchings for the bipartite graph ℬ(k) consisting of the middle two levels of the Boolean lattice on 2k+1 elements are constructed and counted. This research is part of an ongoing effort to show that ℬ(k) is Hamiltonian.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 20
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 59-68 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; minimal cutset ; chain complete ; special points ; regular posets ; Menger's theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract If P is a poset, the associated PT-order is the quasi order ⊴ in which a ⊴ b holds if every maximal chain of P which passes through a also passes through b. P is special if whenever A is a chain in P and a=sup A or inf A, then there is b ∈ A such that b ⊴ a. It is proved that if P is chain complete and special then the set of ⊴-maximal elements is ⊴-dominating and contains a minimal cutset. As corollaries of this, we give partial answers to (i) a question of Rival and Zaguia by showing that if P is regular and special every element is in a minimal cutset and (ii) a question of Brochet and Pouzet by showing that if P is chain complete and special then it has the Menger property.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 21
    Digitale Medien
    Digitale Medien
    Springer
    Journal of theoretical probability 8 (1995), S. 77-96 
    ISSN: 1572-9230
    Schlagwort(e): Random walk ; diffusion ; spectral density ; graphs ; fractal dimensions
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract This paper continues the study of exponentsd(x), d ω (x), d R (x) andd μ (x) for graphG; and the nearest neighbor random walk {X n } n∈N onG, if the starting pointX 0=x is fixed. These exponents are responsible for the geometric, resistance, diffusion and spectral properties of the graph. The main concern of this paper is the relation of these exponents to the spectral density of the transition matrix. A series of new exponentse, e ω ,e R ,e μ are introduced by allowingx to vary along the vertices. The results suggest that the geometric and resistance properties of the graph are responsible for the diffusion speed on the graph.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 22
    Digitale Medien
    Digitale Medien
    Springer
    Order 1 (1985), S. 235-247 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Chain ; antichain ; cutset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A subset A of an ordered set P is a cutset if each maximal chain of P meets A; if, in addition, A is an antichain call it an antichain cutset. Our principal result is a characterization, by means of a ‘forbidden configuration’, of those finite ordered sets, which can be expressed as the union of antichain cutsets.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 23
    Digitale Medien
    Digitale Medien
    Springer
    Order 1 (1985), S. 317-331 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 60C05 ; Partially ordered set ; probabilistic methods ; dimension
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Letk andn be positive integers and fix a setS of cardinalityn; letP k (n) be the (partial) order onS given by the intersection ofk randomly and independently chosen linear orders onS. We begin study of the basic parameters ofP k (n) (e.g., height, width, number of extremal elements) for fixedk and largen. Our object is to illustrate some techniques for dealing with these ‘random orders’ and to lay the groundwork for future research, hoping that they will be found to have useful properties not obtainable by known constructions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 24
    Digitale Medien
    Digitale Medien
    Springer
    Order 1 (1985), S. 371-375 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; chain ; antichain ; cutset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract It is shown that ifP is a poset containing noN, then every minimal cutset inP is an antichain, that the converse also holds whenP is finite, and that this converse fails in general.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 25
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 25-40 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 05C20 ; 05C38 ; Order ; diagram ; graph ; orientation ; cycle
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each κ≥1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called κ-good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers χκ, especially for x 2. There exist graphs that satisfy these inequalities for κ=2 but are not covering graphs. We show also that x 2 cannot be bounded by a function of x=x 1. A construction of Nešetřil and Rödl is used to show that x 2 is not bounded by a function of the girth.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 26
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 387-402 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; linear extension ; correlation ; universal correlation ; Graham, Yao, and Yao inequality ; xyz inequality
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Posets $$A,{\text{ }}B \subseteq X{\text{ x }}X$$ are said to be correlated with respect to another poset R on X (we write A↑ R B) if P(R∪A) P(R∪B)≤P(R∪A∪B) P(R). Here P(S) is the probability that a randomly chosen bijection from X to the totally ordered set with |X| elements is a linear extension of S. We study triples (A, B, R) such that A ↑ R B holds for all extensions S of R (we write A $$\begin{array}{*{20}c} \uparrow \\ \uparrow \\ \end{array}$$ R B). Two well-known correlation inequalities, the xyz inequality and an inequality of Graham, Yao, and Yao, can be considered as giving cases when this relation holds. We show when the Graham, Yao, and Yao inequality holds strictly. Our main result is a classification of all R such that (a, b) $$\begin{array}{*{20}c} \uparrow \\ \uparrow \\ \end{array}$$ R (c, d) holds, where a, b, c, d are elements of X.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 27
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 15-20 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partially ordered set
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Let P be a partially ordered set. Define k = k (P) = max p∈ |{x ∈ P : p 〈 x or p = x}|, i.e., every element is comparable with at most k others. Here it is proven that there exists a constant c (c 〈 50) such that dim P 〈 ck(log k)2. This improves an earlier result of Rödl and Trotter (dim P ≤2 k 2+2). Our proof is nonconstructive, depending in part on Lovász' local lemma.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 28
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 269-274 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partial order ; fixed point ; comparability graph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We show that the fixed point property is comparability invariant for finite ordered sets; that is, if P and Q are finite ordered sets with isomorphic comparability graphs, then P has the fixed point property if and only if Q does. In the process we give a characterization of comparability invariants which can also be used to give shorter proofs of some known results.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 29
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 21-22 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Dimension ; width ; chain-covering number
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A partially ordered set with no infinite antichains may have arbitrarily large dimension.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 30
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 21-38 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ladder ; cutset ; 2-cutset property ; chain ; antichain
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An ordered set P is said to have the 2-cutset property if for every element x of P there is a subset S of P whose elements are noncomparable to x, such that |S|≤2 and such that every maximal chain in P meets {x}∪S. It is shown that if P has the 2-cutset property and has width n then P contains a ladder of length [1/2(n−3)].
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 31
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1988), S. 315-318 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Circle containment order ; poset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract 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 thatx≤y 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.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 32
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 173-186 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; retract ; variety ; obstruction
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We use the technique of ‘χ-Embeddings’ to study retracts and varieties of ordered sets. We investigate the class of all ordered sets $$Q$$ which are retract of every ordered set in which $$Q$$ is ‘χ-Embedded’.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 33
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1989), S. 369-380 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; linear extension ; semiorder ; 1/3–2/3 conjecture ; partially ordered set
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A well-known conjecture of Fredman is that, for every finite partially ordered set (X, 〈) which is not a chain, there is a pair of elements x, y such that P(x〈y), the proportion of linear extensions of (X, 〈) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, 〈) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 34
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 31-37 
    ISSN: 1572-9273
    Schlagwort(e): 05A05 ; 06A10 ; Cutset ; Boolean lattice
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An informative new proof is given for the theorem of Nowakowski that determines for all n and k the minimum size of a cutset for an element A with |A|=k of the Boolean algebra B n of all subsets of {1,...,n}, ordered by inclusion. An inequality is obtained for cutsets for A that is reminiscent of Lubell's inequality for antichains in B n. A new result that is provided by this approach is a list of all minimum cutsets for A.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 35
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1989), S. 349-361 
    ISSN: 1572-9273
    Schlagwort(e): 05C10 ; 06A10 ; Convex Hasse representations ; Kuratowski type results for Hasse diagrams
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 36
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 265-275 
    ISSN: 1572-9273
    Schlagwort(e): 05C75 ; O5C99 ; 06A10 ; Upper bound graph ; multigraph ; poset ; chordal graph ; interval graph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The study of upper bound graphs of posets can be extended naturally to multigraphs. This paper characterizes such upper bound multigraphs, shows they determine the associated posets up to isomorphism, and extends results of D. Scott to characterize posets having chordal or interval upper bound multigraphs.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 37
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 235-237 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Circle containment order ; poset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A partially ordered set P is called a circle containment order provided one can assign to each x∈P a circle C x so that $$x \leqslant y \Leftrightarrow C_x \subseteq C_y $$ . We show that the infinite three-dimensional poset N 3 is not a circle containment order and note that it is still unknown whether or not [n]3 is such an order for arbitrarily large n.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 38
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 1-14 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Fixed point ; irreducible element ; dismantlability ; cutset ; retraction ; crown
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract There exist exactly eleven (up to isomorphism and duality) ordered sets of size ≤10 with the fixed point property and containing no irreducible elements.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 39
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 39-47 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Inclusion orders ; circle orders ; angle orders
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A poset is a circle order if its points can be mapped into circular disks in the plane so that x〈y in the poset precisely when x's circular disk is properly included in y's; the poset is an angle order if its points can be mapped into unbounded angular regions that preserve 〈 by proper inclusion. It is well known that many finite angle orders are not circle orders, but has been open as to whether every finite circle order is an angle order. This paper proves that there are finite circle orders that are not angle orders.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 40
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 91-99 
    ISSN: 1572-9273
    Schlagwort(e): 08A40 ; 06A10 ; Clones ; crowns ; tences ; generators
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In this paper we study the clones of all order preserving operations for crowns and fences. By presenting explicit generating sets, we show that these clones are finitely generated. The case of crowns is particularly interesting because they admit no order preserving near unanimity operations. Various related questions are also discussed. For example, we give a new proof of a theorem of Duffus and Rival which states that crowns are irreducible.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 41
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 235-240 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 52A37 ; Order ; sphere ; partially ordered set ; space-time
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Ann-sphere order is a finite partially ordered set representable by containment ofn-spheres in Euclidean (n+1)-space. We present a sequence {P i } of ordered sets such that eachP i is ann-sphere order only forn≥i; one consequence is that we are able to determine the dimension of a Euclidean space-time manifold from the finite suborders of its causality order.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 42
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 165-171 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 60C05 ; Partially ordered set ; diameter ; random structures
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract 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.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 43
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 129-144 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; linear extension ; correlation ; universal correlation ; Winkler's Theorem ; universal negative correlation
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Posets A, B⫇X×X, with X finite, are said to be universally correlated (A↑B) if, for all posets R over X, (i.e., all posets R⫇Y×Y with X⫇Y), we have P(R∪A) P(R∪B)≤P(R∪A∪B) P(R). Here P(R∪A), for instance, is the probability that a randomly chosen bijection from Y to the totally ordered set with |Y| elements is a linear extension of R∪A. We show that A↑B iff, for all posets R over X, P(R∪A) P(R∪B)≤P(R∪A∪B) P(R∪(A∩B)). Winkler proved a theorem giving a necessary and sufficient condition for A↑B. We suggest an alteration to his proof, and give another condition equivalent to A↑B. Daykin defined the pair (A, B) to be universally negatively correlated (A B) if, for all posets R over X, P(R∪A) P(R∪B)≥P(R∪A∪B) P(R∪(A∩B)). He suggested a condition for A↓B. We give a counterexample to that conjecture, and establish the correct condition. We write A↓B if, for all posets R over X, P(R∪A) P(R∪B)≥P(R∪A∪B) P(R). We give a necessary and sufficient condition for A↓B. We also give constructive techniques for listing all pairs (A, B) satisfying each of the relations A↑B, A↓B, and A↓B.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 44
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 321-322 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 05C99 ; Covering graph ; order orientation ; extremal problems
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Every graph G may be transformed into a covering graph either by deletion of edges or by subdivision. Let Π E (G) and Π V (G) denote corresponding minimal numbers. We prove Π E (G) = Π V (G) for every graph G.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 45
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 1-8 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; N-free poset ; linear extension ; Jump number ; matroid ; greedy algorithm ; Rado-Edmonds theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Let L=x 1 x 2...x n be a linear extension of a poset P. Each pair (x i , x i+1) such that x i ≮ x i+1in P is called a jump of L. It is well known that for N-free posets a natural ‘greedy’ procedure constructing linear extensions yields a linear extension with a minimum number of jumps. We show that there is a matroid corresponding to any N-free poset and apply the Rado-Edmonds Theorem to obtain another proof of this result.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 46
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 61-67 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; multifunction ; fixed point ; chain-completeness
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Sufficient conditions for the fixed point property for products of two partially ordered sets are proved. These conditions are formulated in terms of multifunctions (functions with non-empty sets as values).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 47
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 119-122 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Chordal bipartite graph ; elimination scheme ; crown
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We prove that a bipartite graph is chordal if and only if it has an elimination scheme. This leads to a polynomial algorithm to recognize whether an ordered set is cycle-free.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 48
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 145-164 
    ISSN: 1572-9273
    Schlagwort(e): 06A05 ; 06A10 ; Ordered sets ; linear extension ; greedy dimensions
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Every linear extension L: [x 1〈x 2〈...〈x m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0≤i〈m, choose x i+1 as a minimal element of P−{x j :j≤i}. A linear extension is said to be greedy, if we also require that x i+1 covers x i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P−A|≥2, we show that the greedy dimension of P does not exceed |P−A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|≥4. If the width of P−A is n and n≥2, we show that the greedy dimension of P does not exceed n 2+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n−1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 49
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 243-248 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; chain ; antichain ; width ; cutset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The partially ordered set P is an (α, β, γ) ordered set if the width of P≥α, the length of any chain of P≤β and the cut-set number ≤γ. We will prove that if P is an (α, β, γ) ordered set then P contains a ‘simple’ (α, β, γ) ordered set and use this result to prove that if P has the 3 cutset property, then width of P ≤ length of P+3.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 50
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 245-255 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 60C05 ; Poset ; diagram ; covering graph ; random graph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n -1+η(n) ,where η(n) is bounded away from 0, then there is a constant k 0〉0 such that, for a.e. G p , c(G p )≥k 0 n 1+η(n) .In other words, to make G p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n -1+η(n) , where η(n)→0, thenc(G p )=o(n 1+η(n) ), almost surely.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 51
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 245-255 
    ISSN: 1572-9273
    Schlagwort(e): 05C55 ; 05C70 ; 06A10 ; Decomposition ; Ramsey theory ; graph ; finite set system ; partially ordered set ; monotone sequence ; Δ-system ; chain ; antichain ; sub-k coloring
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Every partially ordered set P on at least (1+o(1))n 3 elements can be decomposed into subposets of size n that are ‘almost’ chains or antichains. This lower bound on P is asymptotically best possible. Similar results are presented for other types of combinatorial structures.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 52
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 305-315 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; maximal chain ; cutset ; Menger's theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract It is shown that, if an ordered set P contains at most k pairwise disjoint maximal chains, where k is finite, then every finite family of maximal chains in P has a cutset of size at most k. As a corollary of this, we obtain the following Menger-type result that, if in addition, P contains k pairwise disjoint complete maximal chains, then the whole family, M (P), of maximal chains in P has a cutset of size k. We also give a direct proof of this result. We give an example of an ordered set P in which every maximal chain is complete, P does not contain infinitely many pairwise disjoint maximal chains (but arbitrarily large finite families of pairwise disjoint maximal chains), and yet M (P) does not have a cutset of size 〈x, where x is any given (infinite) cardinal. This shows that the finiteness of k in the above corollary is essential and disproves a conjecture of Zaguia.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 53
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1989), S. 345-348 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C15 ; Preemptive scheduling ; interval order
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 54
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 245-263 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68E05 ; Bipartite graph ; Bruhat order ; elementary operations
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Consider two partially ordered setsP, Q and a number of edges connecting some of the points ofP with some of the points ofQ. This yields a bipartite graph. Some pairs of the edges may cross each other because their endpoints atP andQ are oppositely ordered. A natural decrossing operation is to exchange the endpoints of these edges incident atQ, say. This is called a switch. A left lift of an edge means to replace its starting point atP by a larger starting point. A right lift is defined symmetrically for the endpoints atQ. The operation of adding an edge cannot, informally, be explained better. Assume we are given two bipartite graphs π, σ on the node setPσQ. We show that for certain pairs (P, Q) of finite posets, a neat necessary and sufficient criterion can be given in order that σ is obtainable from π by the sequence of elementary operations just defined. A recent characterization of the Bruhat order of the symmetric group follows as a special case.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 55
    Digitale Medien
    Digitale Medien
    Springer
    Order 12 (1995), S. 189-210 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Boolean ordered set ; distributive ordered set ; ideal ; prime ideal ; maximal ideal ; representation by sets
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Boolean ordered sets generalize Boolean lattices, and distributive ordered sets generalize distributive lattices. Ideals, prime ideals, and maximal ideals in ordered sets are defined, and some well-known theorems on Boolean lattices, such as the Glivenko-Stone theorem and the Stone representation theorem, are generalized to Boolean ordered sets. A prime ideal theorem for distributive ordered sets is formulated, and the Birkhoff representation theorem is generalized to distributive ordered sets. Fundamental are the embedding theorems for Boolean ordered sets and for distributive ordered sets.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 56
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 9-23 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Jump number ; substitution decomposition
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 57
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 199-210 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06A23 ; Poset ; lower end ; directed ; ideal ; chain ; well-ordered ; extension ; completion ; recycling map ; union complete
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A standard extension for a poset P is a system Q of lower ends (‘descending subsets’) of P containing all principal ideals of P. An isomorphism ϕ between P and Q is called recycling if ∪ϕ[Y]∈Q for all Y∈Q. The existence of such an isomorphism has rather restrictive consequences for the system Q in question. For example, if Q contains all lower ends generated by chains then a recycling isomorphism between P and Q forces Q to be precisely the system of all principal ideals. For certain standard extensions Q, it turns out that every isomorphism between P and Q (if there is any) must be recycling. Our results include the well-known fact that a poset cannot be isomorphic to the system of all lower ends, as well as the fact that a poset is isomorphic to the system of all ideals (i.e., directed lower ends) only if every ideal is principal.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 58
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 249-255 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Partially ordered set (poset) ; antichain ; dual transportation problem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract For any finite partially ordered set S we display a dual transportation system of linear inequalities, and a bijection A(x) from the maximal integer-valued solutions x of this system onto the ‘maximal sequences’ of k antichains in S. This provides a simple translation to a dual transportation problem of the problem: find a maximum weight union of k antichains.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 59
    Digitale Medien
    Digitale Medien
    Springer
    Order 2 (1985), S. 367-385 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06B99 ; 06C10 ; Geometric lattice ; matroid ; strong map ; shellable ; Möbius function
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We define geometric semilattices, a generalization of geometric lattices. The poset of independent sets of a matroid is another example. We prove several axiomatic and constructive characterizations, for example: geometric semilattices are those semilattices obtained by removing a principal filter from a geometric lattice. We also show that all geometric semilattices are shellable, unifying and extending several previous results.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 60
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 135-153 
    ISSN: 1572-9273
    Schlagwort(e): 05C20 ; 05C38 ; 06A10 ; Graph ; orientation ; circuit ; maximal vertex ; pushing down ; order ; diagram
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We study the operation of pushing down elements in the diagram of a finite ordered set. Two natural questions about this operation are, ‘Which orientations of the underlying graph can be obtained from a given orientation by pushing down?’ and ‘Which sets of vertices can become the sets of maximal elements in such orientations?’. For both questions thére are easy necessary conditions. We show that these conditions are also sufficient. The results are extended to cover all induced subgraphs and arbitrary orientations of a finite graph.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 61
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 227-234 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Jump number ; tower number
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The maximum jump number of ordered sets having width w and tower number t, denoted by s(w, t), satisfies $$c_l tw\lg w \leqslant s\left( {w,t} \right) \leqslant tw\lg w$$ for some positive constants c 1 and c 2. Specifically, we can obtain c 1=1/8 and c 2〈11/10. When w and t are sufficiently large and w is a power of 2, then $$\left( {\frac{1}{2} - \varepsilon } \right)tw\lg w \leqslant s\left( {w,t} \right) 〈 \frac{7}{{10}}tw\lg w$$ This gives an answer to a problem posed by W. T. Trotter ([3], Problem 15).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 62
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 269-281 
    ISSN: 1572-9273
    Schlagwort(e): 05C75 ; 05C99 ; 06A10 ; Poset ; subposet ; m-subposet ; upper bound graph ; graph ; subgraph ; induced subgraph ; digraph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Competition graphs of transitive acyclic digraphs are strict upper bound graphs. This paper characterizes those posets, which can be considered transitive acyclic digraphs, which have upper bound graphs that are interval graphs. The results proved here may shed some light on the open question of those digraphs which have interval competition graphs.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 63
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1987), S. 321-330 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; diagram ; NP-completeness
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A diagram is an undirected graph corresponding to the covering relation of a finite poset. We prove that three decision problems related to diagrams are NP-complete.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 64
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1987), S. 359-367 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Ordered set ; jump number ; matching ; dynamic programming ; bipartite permutation graphs
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Let L=u 1 , u 2 , ..., u k be a linear extension of a poset P. Each pair (u i , u i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 65
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 31-35 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partial order ; linear extension ; monotone function ; acyclic function
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Given a poset (A, r) and an acyclic r-monotone function f: A→A, we prove that r can be extended to a linear order R with xRy⇛f(x)Rf(y) for all x, y∈A.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 66
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 101-106 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; width ; fixed point ; chain-completeness ; four-crown tower ; belfry
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We consider the fixed point property (FPP) in an ordered set of width two (every antichain contains at most two elements). The necessary condition of the FPP and a number of equivalent conditions to the FPP in such sets is established. The product theorem is proved, as well.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 67
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 285-291 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partial order ; deficiency ; incomparable pairs
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The deficiency of a partial order is the number of incomparable pairs. Another measure, the spread of a partial order is defined and its relation to the deficiency is established. In certain cases which arise naturally in the analysis of various sorting and selection algorithms where the partial order is only implicitly defined, the spread of the partial order is easier to estimate directly and provides a convenient way to estimate the deficiency.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 68
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 17-20 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06A23 ; Lattice ; order dimension ; least size
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We investigate the behavior of f(d), the least size of a lattice of order dimension d. In particular we show that the lattice of a projective plane of order n has dimension at least n/ln(n), so that f(d)=O(d) 2 log2 d. We conjecture f(d)=θ(d 2 ), and prove something close to this for height-3 lattices, but in general we do not even know whether f(d)/d→∞.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 69
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 33-43 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C05 ; Diagram ; tree ; orientation ; width ; algorithm
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract There are 2 n-1 ways in which a tree on n vertices can be oriented. Each of these can be regarded as the (Hasse) diagram of a partially ordered set. The maximal and minimal widths of these posets are determined. The maximal width depends on the bipartition of the tree as a bipartite graph and it can be determined in time O(n). The minimal width is one of [λ/2] or [λ/2]+1, where λ is the number of leaves of the tree. An algorithm of execution time O(n + λ2 log λ) to construct the minimal width orientation is given.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 70
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 143-147 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partial order ; dimension ; N-free
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The dimension of a partial order can be multiplied by an arbitrarily large factor when edges are subdivided.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 71
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 239-244 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Poset ; structural decomposition ; characterization
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In this paper we show that the number of pairwise nonisomorphic two-dimensional posets with n elements is asymptotically equivalent to 1/2n!. This estimate is based on a characterization, in terms of structural decomposition, of two-dimensional posets having a unique representation as the intersection of two linear extensions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 72
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 289-304 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 54D30 ; Maximal chain ; cutset ; Menger's theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We prove the following results which are related to Menger's theorem for (infinite) ordered sets. (i) If the space of maximal chains of an ordered set is compact, then the maximum number of pairwise disjoint maximal chains is finite and is equal to the minimum size of a cutset, (i.e. a set which meets all maximal chains). (ii) If the maximal chains pairwise intersect, then the intersection of finitely many is never empty. One corollary of (ii) is that, if the maximal chains pairwise intersect and if one of the maximal chains is complete, then there is an element common to all maximal chains.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 73
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1989), S. 363-368 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 60F20 ; Partially ordered set ; random structure ; 0–1 law
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We show that the 0–1 law fails in random orders of fixed dimension k, k≥3. In particular, we give an example of a first-order sentence ϕ, in the language of partial orders, which cannot have limiting probability 0 or 1 among random orders of dimension 3.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 74
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1989), S. 407-423 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06C99 ; 06D99 ; Modular ordered set ; distributive ordered set ; strong subset ; LU subset
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract As modular and distributive ordered sets generalize modular and distributive lattices, it is a natural question to ask whether there exist some ‘forbidden configurations’ for those ordered sets. We present such configurations in the form of strong subsets and LU subsets.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 75
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 15-18 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Linear extension ; promotion ; comparability graph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The number e(P) of linear extensions of a finite poset P is expressed in terms of e(Q) for certain smaller posets Q. The proof is based on M. Schützengerger's concept of promotions of linear extensions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 76
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 209-218 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; pagenumber ; booknumber ; planarity ; linear extension ; linear layout
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract General bounds for the pagenumber of an ordered set are developed. One bound is derived by first showing that the maximum number of edges in the diagram of a planar ordered setP is 2v(P)-2-ht(P). A construction is given to show that the pagenumber of the product ofn chains is no more than 2n-2. Lastly, some open questions are discussed.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 77
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 241-244 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Linear extensions ; comparability graph
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In this note, we prove that the comparability graph of a posetP has less edges than that of a posetQ on the same set of elements, thenP has more linear extensions thanQ. This solves a problem posed by Kelly [1].
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 78
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 295-303 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Depth-first linear extension ; greedy linear extension ; ordered set ; NP-complete
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We show that the problems of deciding whether an ordered set has at leastk depth-first linear extensions and whether an ordered set has at leastk greedy linear extensions are NP-hard.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 79
    Digitale Medien
    Digitale Medien
    Springer
    Positivity 3 (1999), S. 65-81 
    ISSN: 1572-9281
    Schlagwort(e): diffusion ; parabolic ; asymptotic behaviour ; nonlocal
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The goal of this paper is to study diffusion problems associated with nonlinear diffusions of nonlocal type. We give existence and uniqueness results for these kind of problems and investigate the asymptotic behaviour.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 80
    Digitale Medien
    Digitale Medien
    Springer
    Order 1 (1985), S. 229-233 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Partially ordered sets ; imbedding ; embedding ; linear extension
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract An imbedding of a poset P in the integers is a one-to-one order presevring map from P into the integers. Such a map always exists when P is finite and, moreover, certain imbeddings of subsets of finite P can be extended to imbeddings of the whole of P. D. E. Daykin has asked when an imbedding in the integers of a finite subset of a countable poset can be extended to the whole poset. This paper answers Daykin's question and some related questions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 81
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 155-158 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Comparability graph ; ordered set
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We study some invariants of finite comparability graphs.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 82
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 23-32 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 06B05 ; Meet distributive lattices ; convex geometries ; convex dimension
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 83
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 75-83 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 54D30 ; Ordered set ; maximal chain ; cutset ; Menger's theorem
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract It is shown that if a chain complete ordered set does not have k+1 pairwise disjoint maximal chains for some finite k, then the minimum size of a cutset is equal to the maximum size of a collection of pairwise disjoint maximal chains. This answers a question of Pouzet and Zaguia.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 84
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 143-154 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68C25 ; Jump number ; greedy linear extensions ; Dilworth posets ; satisfiability
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 85
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 195-206 
    ISSN: 1572-9273
    Schlagwort(e): 68C15 ; 06A10 ; Posets ; preemptive ; scheduling
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract In scheduling jobs subject to precedence constraints that form a partial order, it is advantageous to interrupt (preempt) jobs, and return to complete them at a later time in order to minimize total completion time. It is clearly desirable to see that such preemptive scheduling by finitely many machines requires only intervals of work, and not a more general assignment of tasks over measurable sets, for optimal completion. It is a deeper fact that arbitrarily small intervals are required for a fixed number of machines m〉-3 for optimal preemptive scheduling. On the other hand, if the number of jobs is fixed, say n, then it is intuitively clear that it suffices to use only comparatively large intervals (but less clear ‘how large’ will suffice!). The authors address these and certain related questions.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 86
    Digitale Medien
    Digitale Medien
    Springer
    Order 4 (1987), S. 221-231 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Order preserving maps ; fixed point property ; product
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract This problem motivates the present work: If ordered sets X and Y both have the fixed point property for order preserving maps has their product as well? Here we present a related condition — the so-called strong fixed point property — which arises from naive attempts to solve the problem. We are concerned with determining the nature and extent of this property. Several questions are raised concerning its relation to the fixed point property and other conditions such as dismantlability and contractibility.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 87
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 149-161 
    ISSN: 1572-9273
    Schlagwort(e): 05C45 ; 05C70 ; 06A10 ; Hamiltonian cycle ; Boolean lattice ; lexicographic matching
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract For any positive integer k let B(k) denote the bipartite graph of k- and k+1-element subsets of a 2k+1-element set with adjacency given by containment. It has been conjectured that for all k, B(k) is Hamiltonian. Any Hamiltonian cycle would be the union of two (perfect) matchings. Here it is shown that for all k〉1 no Hamiltonian cycle in B(k) is the union of two lexicographic matchings.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 88
    Digitale Medien
    Digitale Medien
    Springer
    Order 5 (1988), S. 225-234 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Interval order ; circle order ; geometry
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A finite poset is an interval order if its point can be mapped into real intervals so that x〈y in the poset precisely when x's interval lies wholly to the left of y's; the poset is a circle order if its points can be mapped into circular disks in the plane so that x〈y precisely when x's circular disk is properly included in y's. This note proves that every finite interval order is a circle order.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 89
    Digitale Medien
    Digitale Medien
    Springer
    Order 3 (1986), S. 257-267 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Ordered set ; chain ; core ; cutset ; fixed point ; chain-completeness ; dismantlability ; ordered sum ; fixed point property
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract The purpose of this paper is the analysis and application of the concepts of a core (a pair of chains) and cutset in the fixed point theory for posets. The main results are: (1) (Theorem 3) If P is chain-complete and (*), it contains a cutset S such that every nonempty subset of S has a join or a meet in P, then P has the fixed point property (FPP), (2) (Theorem 5) If P or Q is chain-complete, Q satisfies (*) and both P and Q have the FPP, then P x Q has the FPP. (3) (Theorem 6) Let P or Q be chain-complete and there exist p∈P and a finite sequence f 1, f 2, ..., f n of order-preserving mappings of P into P such that $$\left( {\forall x\varepsilon P} \right)x \leqslant f_1 \left( x \right) \geqslant f_2 \left( x \right) \leqslant \cdots \geqslant f_n \left( x \right) \leqslant p$$ If P and Q have the FPP then P x Q has the FPP. (4) (Theorem 7) If T is an ordered set with the FPP and {P t :t∈T} is a disjoint family of ordered sets with the FPP then its ordered sum ∪{P t :t∈T} has the FPP.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 90
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 227-233 
    ISSN: 1572-9273
    Schlagwort(e): 05A05 ; 05C45 ; 06A10 ; Combinatorial generation ; alternating permutation ; transposition
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract A permutationπ 1 π 2...π n is alternating ifπ 1〈π 2〉π 3〈π 4.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 91
    Digitale Medien
    Digitale Medien
    Springer
    Order 6 (1989), S. 277-293 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; Order dimension ; Ferrers dimension ; Cartesian product
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract It is known that for incidence structures $$\mathbb{K}$$ and $$\mathbb{L}$$ , max $$\{ f{\text{ dim }}\mathbb{K}{\text{, }}f{\text{ dim }}\mathbb{L}{\text{\} }} \leqslant {\text{ }}f{\text{ dim }}\mathbb{K}{\text{ }}x{\text{ }}\mathbb{L} \leqslant f{\text{ dim }}\mathbb{K}{\text{ + }}f{\text{ dim }}\mathbb{L}$$ , wheref dim stands for Ferrers relation. We shall show that under additional assumptions on $$\mathbb{K}$$ and $$\mathbb{L}$$ , both bounds can be improved. Especially it will be shown that the square of a three-dimensional ordered set is at least four-dimensional.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 92
    Digitale Medien
    Digitale Medien
    Springer
    Order 13 (1996), S. 33-39 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 05A05 ; 05C55 ; zero-sum ; monotone sequence ; partially ordered set (posets)
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Bialostocki proposed the following problem: Let n≥k≥2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|≥p(n, k) and every Z k -coloring f: P → Z k there exists either a chain or an antichain A, |A|=n and ∑ a∈A f(a) ≡ 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k−2)2−c(k) ≤ p(n, k) ≤ (n+k−2)2+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 93
    Digitale Medien
    Digitale Medien
    Springer
    Order 13 (1996), S. 209-218 
    ISSN: 1572-9273
    Schlagwort(e): 06A10 ; 68Q15 ; (Partially) ordered set ; fixed point property ; order-preserving map ; complexity ; NP-complete
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract It is NP-complete to determine whether a given ordered set has a fixed point free order-preserving self-map. On the way to this result, we establish the NP-completeness of a related problem: Given ordered sets P and Q with t-tuples (p 1, ... , p t) and (q 1, ... , q t) from P and Q respectively, is there an order-preserving map f: P→Q satisfying f(p i)≥q i for each i=1, ... , t?
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 94
    Digitale Medien
    Digitale Medien
    Springer
    Computational & mathematical organization theory 5 (1999), S. 361-384 
    ISSN: 1572-9346
    Schlagwort(e): bandwagons ; diffusion ; fads ; organizational collectivities ; reputation ; unprofitable innovations
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik
    Notizen: Abstract Bandwagon innovation diffusion is characterized by a positive feedback loop where adoptions by some actors increase the pressure to adopt for other actors. In particular, when gains from an innovation are difficult to quantify, such as implementing quality circles or downsizing practices, diffusion is likely to occur through a bandwagon process. In this paper we extend Abrahamson and Rosenkopf&2018;s (1993) model of bandwagon diffusion to examine both reputational and informational influences on this process. We find that the distribution of reputations among the set of potential adopters affects the extent of bandwagon diffusion under conditions of moderate ambiguity, and we find that bandwagons occur even when potential adopters receive information about others&2018; unprofitable experiences with the innovation.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 95
    Digitale Medien
    Digitale Medien
    Springer
    Archive of applied mechanics 69 (1999), S. 121-132 
    ISSN: 1432-0681
    Schlagwort(e): Key words large deformations ; porous material ; diffusion ; change of porosity ; filtration ; perturbation method
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Maschinenbau
    Notizen: Summary We present an example of the solution of a boundary value problem for a two-component porous material with large deformation of the skeleton. This example demonstrates the application of a consistent lagrangian description of porous materials which has been proposed earlier. Simultaneously, we demonstrate the important role of the balance equation of porosity which is an essential part of the thermodynamical model of porous materials proposed earlier. We show as well that a modified set of boundary conditions for permeable boundaries yields a solution of field equations which agrees qualitatively with expectations for the problem of axisymmetric stationary filtration. On the basis of a numerical evaluation of solution we indicate the existence of an instability of the model for very large porosities which could not be explained in this work.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 96
    Digitale Medien
    Digitale Medien
    Springer
    Archive of applied mechanics 67 (1997), S. 487-495 
    ISSN: 1432-0681
    Schlagwort(e): Keywords convection ; porous medium ; thermal dispersion ; diffusion ; boundary layer
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Maschinenbau
    Notizen: Summary The effect of surface mass flux on the non-Darcy natural convection over a horizontal flat plate in a saturated porous medium is studied using similarity solution technique. Forchheimer extension is considered in the flow equations. The suction/injection velocity distribution has been assumed to have power function form Bx l , similar to that of the wall temperature distribution Ax n , where x is the distance from the leading edge. The thermal diffusivity coefficient has been assumed to be the sum of the molecular diffusivity and the dynamic diffusivity due to mechanical dispersion. The dynamic diffusivity is assumed to vary linearly with the velocity component in the x direction, i.e. along the hot wall. For the problem of constant heat flux from the surface (n=1/2), similarity solution is possible when the exponent l takes the value −1/2. Results indicate that the boundary layer thickness decreases whereas the heat transfer rate increases as the mass flux parameter passes from the injection domain to the suction domain. The increase in the thermal dispersion parameter is observed to favor the heat transfer by reducing the boundary layer thickness. The combined effect of thermal dispersion and fluid suction/injection on the heat transfer rate is discussed.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 97
    Digitale Medien
    Digitale Medien
    Springer
    Journal of intelligent and robotic systems 17 (1996), S. 309-325 
    ISSN: 1573-0409
    Schlagwort(e): modeling ; camera ; CCD ; subpixel ; simulation ; vision ; image ; diffusion ; CAD ; CIM ; bias
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Maschinenbau
    Notizen: Abstract In this paper we propose a modeling of an acquisition line made up of a CCD camera, a lens and a frame grabber card. The purpose of this modeling is to simulate the acquisition process in order to obtain images of virtual objects. The response time has to be short enough to permit interactive simulation. All the stages are modelised: in the first phase, we present a geometric model which supplies a point to point transformation that provides, for a space point in the camera field, the corresponding point on the plane of the CCD sensor. The second phase consists of modeling the discrete space which implies passing from the continous known object view to a discrete image, in accordance with the different orgin of the contrast loss. In the third phase, the video signal is reconstituted in order to be sampled by the frame grabber card. The practical results are close to reality when compared to image processing. This tool makes it possible to obtain a short computation time simulation of a vision sensor. This enables interactivity either with the user or with software for the design/simulation of an industrial workshop equipped with a vision system. It makes testing possible and validates the choice of sensor placement and image processing and analysis. Thanks to this simulation tool, we can control perfectly the position of the object image placed under the camera and in this way, we can characterise the performance of subpixel accuracy determining methods for object positioning.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 98
    Digitale Medien
    Digitale Medien
    Springer
    Plasma chemistry and plasma processing 16 (1996), S. 195-208 
    ISSN: 1572-8986
    Schlagwort(e): Surface recombination ; nitrogen afterglow ; breakdown time delay ; diffusion ; nitrogen atoms ; secondary electron yield ; Fe, Cu, Al, Au, Mo
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Maschinenbau , Technik allgemein
    Notizen: Abstract The late afterglow in nitrogen with iron electrode is studied by the breakdown time delay method, i.e., by measuring the breakdown time delay td as a function of the afterglow time τ. It is proposed that the cause of the secondary electrons initiating the breakdown is the energy of the surface recombination of nitrogen atoms on the iron electrode. The gas-phase and macrokinetic diffusive models are used to describe the experimental breakdown time delay data. By fitting the theoretical curve to the experimental data: (1) it has been confirmed that the recombination on the molybdenum glass is of the second order and the value of the surface recombination coefficient is determined at 4 mbar; (2) it has been shown that the surface recombination on the iron electrode is of the second order, and the effective recombination coefficients are determined; (3) the analytical form of the recombination coefficient as a function of the adsorption characteristics of surfaces and the pressure of the parent gas has been derived. In addition, the orders of surface recombination on the molybdenum-, aluminum-, and gold-plated electrode were determined by the same method.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 99
    Digitale Medien
    Digitale Medien
    Springer
    Plasma chemistry and plasma processing 16 (1996), S. 417-448 
    ISSN: 1572-8986
    Schlagwort(e): Flame-assisted plasma ; variable properties ; diffusion ; laser-induced fluorescence ; electrostatic probe ; current/voltage characteristics
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Chemie und Pharmazie , Maschinenbau , Technik allgemein
    Notizen: Abstract A well-characterized flame-assisted plasma was developed to understand the role of flow nonuniformities and plasma/wall interactions in plasma devices for use in validation of laser-based Doppler shift spectroscopic methods. A hydrogen/oxygen capillary diffusion flame burner was used as a plasma source, with barium seeded into the reactants to provide a source of ions and electrons. For analysis the plasma was assumed to be a stationary, partially ionized, collision dominated, thermal plasma consisting of barium ions, electrons, and neutrals between two parallel-plate electrodes. The plasma was examined in terms of the continuum equations for ions and electrons, together with Poisson's equation to predict spatial profiles of electron and positive ion density and potential as functions of applied potential. First an analytic solution based on constant plasma properties and negligible difusion was introduced. The model was then extended by including effects of diffusion and variable plasma properties. Experimentally, current/voltage characteristics of the plasma were measured conventionally, relative ion concentration and temperature were measured with laser-induced fluorescence, and local potential distribution was measured using an electrostatic probe. The diffusionless theory predicted well the bulk behavior of the plasma, but not the correct spatial distributions of ion concentration and potential. The extended model produced a more satisfactory fit to the data. At conditions of 1.4 equivalence ratio, 70 torn pressure, 300 ppm seed concentration, and 100–400 V applied potentials, electric fields of the order of 102, 103 V/cm were observed near the powered electrode, and of few tens of V/cm in the hulk of tire plasma. The field strength in the sheath ensures the operation of the Doppler shift diagnostics, once the recommendations tor LIF signal detectability are fulfilled.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 100
    Digitale Medien
    Digitale Medien
    Springer
    Oxidation of metals 47 (1997), S. 427-444 
    ISSN: 1573-4889
    Schlagwort(e): modeling ; numerical techniques ; finite-difference methods ; diffusion ; moving boundary problem ; steam oxidation ; Zircaloy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Maschinenbau
    Notizen: Abstract Numerical solutions of the oxygen-diffusion problem arising in the oxidation of metals at high temperatures are complicated by the change in density as the oxide is formed and the occurrence of moving boundaries separating the different phases. The former complication is resolved by a transformation of the dependent variable and the coordinate, which reduces the problem to a form identical to one without density change. The latter complication is dealt with by demonstrating an analogy with the Stefan problem in heat transfer with phase change in the enthalpy formulation, for which abundant numerical works exist. A finite-difference code is written to solve the resulting equations. It is successfully applied to simulate an oxidation experiment of Zircaloy by steam at 1600°C.
    Materialart: Digitale Medien
    Standort Signatur Erwartet Verfügbarkeit
    BibTip Andere fanden auch interessant ...
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...