Dimension versus size
type: Item
instance of: scholarly article
title: Dimension versus size
zbMATH Open document ID: 0655.06002
DOI: 10.1007/BF00143893
published in: Order
publication date: 1988-01-01T00:00:00Z
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|)\).
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06B23
zbMATH DE Number: 4068941
zbMATH Keywords: least size
zbMATH Keywords: order dimension
author: Zoltán Füredi
author: J. Kahn
reviewed by: Bohumil František Šmarda
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00143893
OpenAlex ID: W1983255178
description: scientific article; zbMATH DE number 4068941