Dimension versus size

DOI10.1007/BF00143893MaRDI QIDQ1109056zbMATH OpenOpenAlexFDO

Authors Zoltán Füredi, J. Kahn

Publication date 1988

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00143893

zbMATH Keywords

least sizeorder dimension

Mathematics Subject Classification ID

Partial orders, general (06A06) Complete lattices, completions (06B23)

Review text

The order dimension of a poset P (dim P) is the least s for which there exist linear extensions \(\sigma_ 1,...,\sigma_ s\) of P (i.e., order preserving bijections \(P\to \{1,...,| P| \})\) such that for all \(p,g\in P\) with \(p\nless g\) there exists \(i\in \{1,...,s\}\) with \(\sigma_ i(p)>\sigma_ i(g)\). The authors investigate also behaviour of f(d), the least size of a lattice of order dimension d. If \(P_ n\) is the lattice of a projective plane of order n then \(\dim P_ n>n/2 \ln (n)\) and \(f(d)=O(d\) 2log 2d). If L is a lattice of height 3 then dim L\(=O(| L|^{1/2} \log | L|)\).

Recommendations

• How small can a lattice of order-dimension n be?
• On an extremal problem for poset dimension
• The order dimension of divisibility
• Planar posets, dimension, breadth and the number of minimal elements
• On the dimensions of ordered sets of bounded degree

Cited in

(32)

• The dimension of the Cartesian product of partial orders
• Dimension may exceed width
• Comparing dimensions of a small category
• The order dimension of the complete graph
• The order dimension of multinomial lattices
• Large-scale regularities of lattice embeddings of posets
• Fractional dimension of partial orders
• On the problem of dimension versus size for lattices
• Size matters!
• The extra-nice dimensions
• The order dimension of divisibility
• A half-space approach to order dimension
• Forcing posets with large dimension to contain large standard examples
• On the sizes of DPDAs, PDAs, LBAs
• Searching in 2-dimensional partial orders
• On the size and shape of drumlins
• Bounds on the k-dimension of products of special posets
• On the order dimension of convex geometries
• scientific article; zbMATH DE number 175746 (Why is no real title available?)
• scientific article; zbMATH DE number 1554930 (Why is no real title available?)
• scientific article; zbMATH DE number 3995740 (Why is no real title available?)
• Size functions
• Order dimension of layered generalized crowns.
• On the order dimension of locally countable partial orderings
• On the dimension of downsets of integer partitions and compositions
• A study of the order dimension of a poset using matrices
• Mathematical Foundations of Computer Science 2005
• The size of SPP
• Large subposets with small dimension.
• On locally presented posets
• Order dimension of orthomodular amalgamations over trees
• Tight embeddings of partial quadrilateral packings

This page was built for publication: Dimension versus size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109056)