A decomposition theorem for partially ordered sets
From MaRDI portal
Publication:2648578
DOI10.2307/1969503zbMath0038.02003OpenAlexW4254807835WikidataQ30040757 ScholiaQ30040757MaRDI QIDQ2648578
Publication date: 1950
Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/1969503
Related Items
Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets, Maximum-sized antichains in minimal posets, Polyhedral proof methods in combinatorial optimization, On k-optimum dipath partitions and partial k-colourings of acyclic digraphs, Decomposing weighted digraphs into sums of chains, Empty monochromatic triangles, Forcing posets with large dimension to contain large standard examples, Monochromatic directed walks in arc-colored directed graphs, Alternating orientation and alternating colouration of perfect graphs, A note on Dilworth's theorem in the infinite case, Optimal space coverage with white convex polygons, Lines, betweenness and metric spaces, Ramsey-type theorems for sets satisfying a geometric regularity condition, Algorithms for some graph theoretical optimization problems (abstract of thesis), A bipartite analogue of Dilworth's theorem, An extended framework for passive asynchronous testing, A structure theorem for posets admitting a ``strong chain partition: a generalization of a conjecture of Daykin and Daykin (with connections to probability correlation inequalities), On the maximum even factor in weakly symmetric graphs, Approximate min-max relations for odd cycles in planar graphs, Maximum union-free subfamilies, The variety generated by planar modular lattices, The zero-divisor graphs of posets and an application to semigroups, Turán-type results for partial orders and intersection graphs of convex sets, Alternating paths along axis-parallel segments, Weak sense of direction labelings and graph embeddings, New bounds on the maximum number of edges in \(k\)-quasi-planar graphs, An Erdős-Gallai theorem for matroids, Generalized Robinson-Schensted-Knuth correspondence, Representing homomorphisms of distributive lattices as restrictions of congruences of rectangular lattices, Erdős-Szekeres theorem for point sets with forbidden subconfigurations, The Jordan-Hölder theorem with uniqueness for groups and semimodular lattices, Lower bounds for randomized algorithms for online chain partitioning, An extremal problem on crossing vectors., Partially ordered sets and stratification, Some order dimension bounds for communication complexity problems, On the complexity of dynamic programming for sequencing problems with precedence constraints, Geodesics in CAT(0) cubical complexes, Linear discrepancy of chain products and posets with bounded degree, Partitioning a weighted partial order, Binary relations: Finite characterizations and computational complexity, On the number of monotone sequences, On the geometric Ramsey numbers of trees, Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game, Perfect zero-divisor graphs, Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture, On Linial's conjecture for spine digraphs, Preperfect graphs, Cut-sets in infinite graphs and partial orders, On Greene-Kleitman's theorem for general digraphs, Finding the largest suborder of fixed width, Utility representation of an incomplete preference relation, Minimum vertex cover in rectangle graphs, Finding common structured patterns in linear graphs, Project scheduling with irregular costs: complexity, approximability, and algorithms, A Nice labelling for tree-like event structures of degree 3, Scheduling tasks with exponential duration on unrelated parallel machines, Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes, On switching paths polyhedra, Two easy duality theorems for product partial orders, Some inequalities for partial orders, NP-completeness properties about linear extensions, Cyclic orders, On the lattice of maximum-sized antichains of a finite poset, Pfaffian systems of \(A\)-hypergeometric equations. I: Bases of twisted cohomology groups., Utility representation of lower separable preferences, A Ramsey-type result for geometric \(\ell\)-hypergraphs, Optimal conclusive sets for comparator networks, Property \(A\) and \(\text{CAT}(0)\) cube complexes., Duality for semiantichains and unichain coverings in products of special posets, Computational complexity of some scheduling problems with multiprocessor tasks, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Monotonicity, Antichain cutsets, A poset-based approach to embedding median graphs in hypercubes and lattices, The matrix of a slim semimodular lattice, On the chromatic number of disjointness graphs of curves, A bipartite analogue of Dilworth's theorem for multiple partial orders, A polynomial bound for untangling geometric planar graphs, On generalized Schur numbers of the equation \(x+ay=z\), Perfectness and imperfectness of unit disk graphs on triangular lattice points, Comparing Dushnik-Miller dimension, Boolean dimension and local dimension, On geometric graph Ramsey numbers, Using formal verification to evaluate the execution time of Spark applications, How to derive finite semimodular lattices from distributive lattices?, Distributive Cauchy lattices, Uniqueness of linear extensions of partial orders, Enumerating fuzzy switching functions and free Kleene algebras, The Sperner property for posets: A probabilistic approach, Networks and chain coverings in partial orders and their products, On the computational complexity of path cover problems, Path-closed sets, Finite cutsets and finite antichains, On the size of jump-critical ordered sets, Inequalities for the greedy dimensions of ordered sets, On partitions and presortedness of sequences, A bound for the Dilworth number, On the complexity of a family of generalized matching problems, ``Poly-unsaturated posets: The Greene-Kleitman theorem is best possible, Decomposing a set of points into chains, with applications to permutation and circle graphs, Some sequences associated with combinatorial structures, On the poset of all posets on \(n\) elements, Some geometric applications of Dilworth's theorem, Families of sets with locally bounded width, Dynamic conflict-free colorings in the plane, An analysis of shift class design problems, Algorithms constructing a representive vector criterion for a binary preference relation, Paths in directed graphs and spectral properties of matrices, On the fractional dimension of partially ordered sets, Optimally balancing assembly lines with different workstations, On some structural properties of a subclass of \(\infty\)-regular languages, A theory of nonmonotonic rule systems. II, Minimal generation of transitive permutation groups, A general theorem on temporal foliations of causal sets, A theory of nonmonotonic rule systems I, Families of chains of a poset and Sperner properties, Substitution and atomic extension on greedy posets, How robust is the n-cube?, Locally perfect graphs, Switchdec polyhedra, A chain decomposition theorem, Passive testing with asynchronous communications and timestamps, Two-sided cells in the affine Weyl group of type \(\tilde A_{n-1}\), Decompositions of partially ordered sets into chains and antichains of given size, Problems on chain partitions, On the approximability of the maximum interval constrained coloring problem, Maximal chains and cutsets of an ordered set: A Menger type approach, A note on perfect orders, ERCW PRAMs and optical communication, The rank of a distributive lattice, Exact and approximation algorithms for the operational fixed interval scheduling problem, Combinatorial inequalities for semimodular lattices of breadth two, Zur Theorie der perfekten Graphen, A partition theorem for ordinals, A short proof of the existence of k-saturated partitions of partially ordered sets, The Ramsey numbers r(P\(_m\),K\(_n\)), On chains and Sperner k-families in ranked posets, Trees and circle orders, On chain and antichain families of a partially ordered set, A construction for partially ordered sets, A lattice-theoretical characterization of the family of cut sets of interval-valued fuzzy sets, Efficient searching using partial ordering, A structure theory for ordered sets, Maximum antichains in posets of quiver representations, COMs: complexes of oriented matroids, Extending the Greene-Kleitman theorem to directed graphs, Local coherence., On the arc-chromatic number of a digraph, The metacompactness of spaces with bases of subinfinite rank, Geometric thickness in a grid, Long cycles in Hamiltonian graphs, Airplane boarding meets express line queues, k-optimal partitions of a directed graph, The queue-number of posets of bounded width or height, Algorithms and bounds for drawing directed graphs, Commutative algebra of generalised Frobenius numbers, Realizable posets, Efficient \(q\)-ary immutable codes, Concerning the size of logical clocks in distributed systems, A greedy reduction algorithm for setup optimization, New clique and independent set algorithms for circle graphs, Gallai-Milgram properties for infinite graphs, Maximum and minimum jump number of posets from matrices, Coflow polyhedra, Matching theory -- a sampler: From Dénes König to the present, Changing and unchanging the diameter of a hypercube, An easy subexponential bound for online chain partitioning, Anchored reactive and proactive solutions to the CPM-scheduling problem, Exact and heuristic methods for solving the robotic assembly line balancing problem, A new fixed point approach for stable networks and stable marriages, License class design: Complexity and algorithms, Search and sweep numbers of finite directed acyclic graphs, On estimating the number of order ideals in partial orders, with some applications, Irreducible posets with large height exist, An extension of Schensted's theorem, The dimension of planar posets, Dimension of the crown \(S^k_n\), Embedding finite posets in cubes, Some theorems on graphs and posets, Some partitions associated with a partially ordered set, Symmetrische Zerlegung von Kettenprodukten, On formal fractions associated with the symmetric groups, On Dilworth's decomposition theorem, On the complexity of posets, Irreducibility and generation in continuous lattices, Equational axioms for classes of Heyting algebras, Weak embeddings and embeddings of finite distributive lattices, Covering digraphs by paths, Another proof of Dilworth's decomposition theorem, Skew chain orders and sets of rectangles, Representing triangulated graphs in stars, Parametrization of knowledge structures, On the n-cutset property, Covering a symmetric poset by symmetric chains, Varieties of solvable Lie rings of finite width, Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers, On the dimension of ordered sets with the 2-cutset property, Finite labelling problem in event structures, An improved algorithm for the jump number problem, Network flow and 2-satisfiability, Covering a poset by interval orders, On the Erdős-Szekeres convex polygon problem, Semiantichains and Unichain Coverings in Direct Products of Partial Orders, Weighted Rooted Trees: Fat or Tall?, A proof of Dilworth's decomposition theorem for partially ordered sets, On Dilworth's theorem in the infinite case, Decompositions of the Boolean lattice into rank-symmetric chains., Partitions Into Chains of a Class of Partially Ordered Sets, Inference of boundaries in causal sets, News about Semiantichains and Unichain Coverings, Connected regular sublattices of Euclidean space, Pairwise Compatibility Graphs: A Survey, Chains and Antichains in the Bruhat Order for Classes of (0, 1)-Matrices, Changing the Depth of an Ordered Set by Decomposition, Two algorithms for LCS consecutive suffix alignment, Estimates in Shirshov height theorem, Partially ordered sets and the independence property, Finding Boundary Elements in Ordered Sets with Application to Safety and Requirements Analysis, New summary measures and datasets for the multi-project scheduling problem, A linear-time parameterized algorithm for computing the width of a DAG, Interval approximations of message causality in distributed executions, Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier, The tensor product of distributive lattices: structural results, k-Quasi-Planar Graphs, Broadcast Transmission to Prioritizing Receivers, Unnamed Item, ON INCIDENCE MODULO IDEAL RINGS, The Hardness of Approximating Poset Dimension, Odd-distance sets and right-equidistant sequences in the maximum and Manhattan metrics, The \(1/3-2/3\) Conjecture for Coxeter groups, Computing and ranking measures of presortedness, Unnamed Item, A Path Cover Technique for LCAs in Dags, Monotone Subsequences in High-Dimensional Permutations, Toric codes from order polytopes, Sperner's Problem forG-Independent Families, Easily Testable Graph Properties, Maximum-Minimum Sätze über Graphen, ON THE COMPLEMENT OF THE ZERO-DIVISOR GRAPH OF A PARTIALLY ORDERED SET, Minimum decomposition of partially ordered sets into chains, SOME WEAKER FORMS OF THE CHAIN (F) CONDITION FOR METACOMPACTNESS, Relating CAT(0) cubical complexes and flag simplicial complexes, Lazy queue layouts of posets, Optimal Linear Extensions by Interchanging Chains, Intersection representation of digraphs in trees with few leaves, Minimizing Setups for Cycle-Free Ordered Sets, Well, Better and In-Between, On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders, On the dimension of vertex labeling of k-uniform dcsl of an even cycle, Shared-Memory Systems and Charts, Addendum to a paper of M. Saks, On the existence of small antichains for definable quasi-orders, A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths, Cardinal Representations for Closures and Preclosures, A unified approach to known and unknown cases of Berge's conjecture, APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS, Graphs defined on groups, Exhaustive testing of almost all devices with outputs depending on limited number of inputs, Extensions of functions of 0-1 variables and applications to combinatorial optimization, Unnamed Item, Transitive-Closure Spanners: A Survey, Matching and spanning in certain planar graphs, Unnamed Item, Unnamed Item, Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems, Remarks on Dilworth's theorem in relation to transversal theory, Unnamed Item, Toric partial orders, Iterated arc graphs, The singular graph of lower triangular, nilpotent matrices, Entropy and phase transitions in partially ordered sets, On the representation of finite distributive lattices, On the Jump Number of Lexicographic Sums of Ordered Sets, Isometric Diamond Subgraphs, Borel Orderings, Multicollision attacks and generalized iterated hash functions, Decidability and ℵ0-categoricity of theories of partially ordered sets, White Space Regions, Topological Properties of Event Structures, Combinatorial Dichotomies in Set Theory, Rings that are sums of two locally nilpotent subrings, Pomset Languages of Finite Step Transition Systems, On Grids in Point-Line Arrangements in the Plane, Inequalities in Dimension Theory for Posets, Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems, A New Framework for Hierarchical Drawings, On Path Partitions and Colourings in Digraphs, On the tame irreducible representations of orders1, Outerstring Graphs are $\chi$-Bounded, Acyclic Digraphs, Plane 3-Trees: Embeddability and Approximation, A survey on pairwise compatibility graphs, Lazy Queue Layouts of Posets, Recent developments on the power graph of finite groups – a survey, Geometric Thickness in a Grid of Linear Area, The secretary problem on an unknown poset, Graded ideals of König type, Annual Meeting of the Association for Symbolic Logic Denver, 1983, Dynamic Conflict-Free Colorings in the Plane, Examples of Jump-Critical Ordered Sets, Onn×nmatrices over a finite distributive lattice, On the parametric complexity of schedules to minimize tardy tasks., The relation between the Jordan structure of a matrix and its graph, The facets and the symmetries of the approval-voting polytope, Erdős--Szekeres theorem with forbidden order types, Linial's conjecture for arc-spine digraphs, Integer partitions and the Sperner property, Slim semimodular lattices. II: A description by patchwork systems, Minimal rationalizations, \( \chi \)-diperfect digraphs, Matchings, cutsets, and chain partitions in graded posets, Dimensionality of ordinal structures, On-line chain partitioning of up-growing interval orders, Lattices of lower finite breadth, Subgroup sum graphs of finite abelian groups, Representing lattices using many-valued relations, Symmetric chain partitions of orthocomplemented posets, Off-diagonal hypergraph Ramsey numbers, Tree-width and dimension, Hamiltonian paths, unit-interval complexes, and determinantal facet ideals, Obituary: R. P. Dilworth, Modular intersection graphs, New characterisations of tree-based networks and proximity measures, Parallel dedicated machines scheduling with chain precedence constraints, On some graph classes related to perfect graphs: a survey, Improved bounds for induced poset saturation, Roller boundaries for median spaces and algebras, Polarization and depolarization of monomial ideals with application to multi-state system reliability, Hierarchically hyperbolic spaces. II: Combination theorems and the distance formula, The width of downsets, On the multi-utility representation of preference relations, Berge's conjecture on directed path partitions -- a survey, Classes of perfect graphs, Vyacheslav Tanaev: contributions to scheduling and related areas, Finite dimensional scattered posets, Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width, Efficient dependency tracking for relevant events in concurrent systems, Timestamping messages and events in a distributed system using synchronous communication, Moving averages in the plane, The Boolean rainbow Ramsey number of antichains, Boolean posets and chains, On visibility and covering by convex sets, Embedding median algebras in products of trees., Representations of primitive posets, On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness, Note on geometric graphs, Balanced convex partitions of lines in the plane, Comparability graphs of lattices, On the strong and the semi-strong path partition conjecture, On lattice path matroid polytopes: integer points and Ehrhart polynomial, Another note on Dilworth's decomposition theorem., Empty monochromatic simplices, Antichains of \((0, 1)\)-matrices through inversions, Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem, Slim semimodular lattices. I. A visual approach, Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs, On the geometric Ramsey number of outerplanar graphs, Quasimorphisms, random walks, and transient subsets in countable groups, Ordered and delayed adversaries and how to work against them on a shared channel, Independent set of intersection graphs of convex objects in 2D, Processor-efficient sparse matrix-vector multiplication, The saturation number of induced subposets of the Boolean lattice, A theory of recursive dimension of ordered sets, Finite convex geometries of circles, On grids in point-line arrangements in the plane, Robust flows over time: models and complexity results, Linear extensions and comparable pairs in partial orders, Interval \(k\)-graphs and orders, Saturation problems in the Ramsey theory of graphs, posets and point sets, The solid-metric dimension, Fractional local dimension, On the comparison of incompatibility of split systems across different numbers of taxa, On the structure of matrices avoiding interval-minor patterns, Forbidden subgraphs of power graphs, Interval stability and interval covering property in finite posets, Turán-type results for complete \(h\)-partite graphs in comparability and incomparability graphs, Two combinatorial problems on posets, Representing point sets on the plane as permutations, Hajós and Ore constructions for digraphs, Superrigidity of actions on finite rank median spaces, The Tits alternative for finite rank median spaces, On Dilworth's coding theorem, Anti-blocking polyhedra, Membership problems for regular and context-free trace languages, Maximal dimensional partially ordered sets. I: Hiraguchi's theorem, Maximal dimensional partially ordered sets. II: Characterization of 2n- element posets with dimension n, A characterization of bivariegated trees, Distributive lattices and Auslander regular algebras, The Tutte-Grothendieck ring, On orthogonal symmetric chain decompositions, Odd-distance and right-equidistant sets in the maximum and Manhattan metrics, Bounding the number of circuits of a graph, A generalization of Hanani's theorem on partial order, Covering arrays on graphs, Computing possible and certain answers over order-incomplete data, On decompositions of matrices over distributive lattices, Submodular functions and rooted trees, The multiple TSP with time windows: vehicle bounds based on precedence graphs, Extreme points of the credal sets generated by comparative probabilities, On a conjecture of Füredi., Linearly related polyominoes, Fast and longest rollercoasters, Disjointness graphs of segments in the space, Complete Amonotonic Decompositions of Compact Continua, Balance constants for Coxeter groups, Fast reliability ranking of matchstick minimal networks, Uniform chain decompositions and applications, Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU, Searching rigid data structures, Absolute retracts for finite distributive lattices and slim semimodular lattices, Unavoidable patterns in complete simple topological graphs, The chain covering number of a poset with no infinite antichains, Approximately counting and sampling knowledge states, On quantitative aspects of a canonisation theorem for edge‐orderings, Apéry sets and the ideal class monoid of a numerical semigroup, Twisted ways to find plane structures in simple drawings of complete graphs, Strongly algebraically closed \(p\)-semilattices, Chain algebras of finite distributive lattices, Dominance drawings for DAGs with bounded modular width, Subsequences in bounded ranges: matching and analysis problems, 2-Layer Graph Drawings with Bounded Pathwidth, On groups with chordal power graph, including a classification in the case of finite simple groups, Max-norm Ramsey theory, Ramsey numbers of cliques versus monotone paths, Blocking and anti-blocking pairs of polyhedra, Unnamed Item, String graphs and incomparability graphs, Locally Convex Topological Lattices, Maximal Independent Collections of Closed Sets, Über reguläre Kettengruppen, On the dimension of partially ordered sets, The structure of Sperner k-families, Finite posets and Ferrers shapes, An Embedding Theorem for Compact Semilattices, Generalized and geometric Ramsey numbers for cycles., Compression using efficient multicasting, Minimizing the number of tardy jobs with precedence constraints and agreeable due dates, On the duality of semiantichains and unichain coverings., Dimension and matchings in comparability and incomparability graphs., \(P\)-partition generating function equivalence of naturally labeled posets, \(k\)-critical graphs in \(P_5\)-free graphs, On Decompositions of Partially Ordered Sets, \(k\)-critical graphs in \(P_5\)-free graphs, Systems of representatives, Hasse Diagram Generators and Petri Nets, Choice mappings of certain classes of finite sets, The structure of Sperner k-families, Unnamed Item, Choice mappings of certain classes of finite sets
