pith. sign in

arxiv: 1705.09167 · v1 · pith:6WB5MXWDnew · submitted 2017-05-25 · 🧮 math.CO · cs.DM

Boolean dimension and local dimension

classification 🧮 math.CO cs.DM
keywords dimensionbooleanlocalposetsboundedclassesrecentresearch
0
0 comments X
read the original abstract

Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted classes of posets. Bounded dimension gives a succinct representation of the poset, admitting constant response time for queries of the form "is $x<y$?". This application motivates looking for stronger notions of dimension, possibly leading to succinct representations for more general classes of posets. We focus on two: boolean dimension, introduced in the 1980s and revisited in recent research, and local dimension, a very new one. We determine precisely which values of dimension/boolean dimension/local dimension imply that the two other parameters are bounded.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.