Posets with large dimension and relatively few critical pairs
type: Item
instance of: scholarly article
title: Posets with large dimension and relatively few critical pairs
zbMATH Open document ID: 0801.06003
DOI: 10.1007/BF01108827
author: Peter Fishburn
author: William T. Trotter
published in: Order
publication date: 1994-12-01T00:00:00Z
review text: The dimension of a poset \(P\) is the minimum number of linear extensions of that poset whose intersection yields \(P\). It is no larger than the collection of incomparable (parallel) pairs \((x,y)\) with the property that \(u<y\) when \(u<x\) and \(x<v\) whenever \(y<u\). For example, if \(S_ n\) is the poset with vertices \(\{a_ 1,\dots, a_ n, b_ n,\dots,b_ n\}\) and \(x<y\) iff \(x= a_ i\); \(y=b_ j\), \(i\neq j\), then \(\dim S_ n= n= | \text{crit} (S_ n)|= |\{ (a_ i, b_ i)\mid i=1, \dots, n\}|\). Including a graph-theoretical approach, the authors are able to apply results and arguments on chromatic numbers to solve the Characterization Problem: for integers \(t\) and \(m\) with \(3\leq t\leq m\leq t+2\), find the minimum set \(P(t,m)\) so that if \(P\) is a poset with \(\dim P =t\) and \(| \text{crit} (P)| =m\), then \(P\) contains a poset in \(P(t,m)\) as a subposet. The conclusions are as follows: If \(m\leq t+1\), then \(P\) contains (a copy of) \(S_ t\) (Theorem 4.2), if \(m\leq 5\) then \(P\) contains \(S_ 3\), \(C\) (the chevron) or \(C^ d\) (the dual, opposite of \(C\)) (Theorem 4.3), while if \(t\geq 4\), then \(P\) contains \(S_ t\), the dimension product \(S_{t-3} \otimes C\) or \(S_{t-3} \otimes C^ d\). The arguments are illustrative of a method that permits global considerations (dimension, linear extensions, etc.) to be localized (critical pairs) by paying close attention to underlying graph-theoretical (diagrammatical) properties and results leading to characterization by substructure containment or noncontainment (i.e., Kuratowski-type) theorems and for which the authors paired this way are also known. It is noted that this work is on the way to better understanding of a conjecture due to Fishburn connecting dimension of posets with numbers of incomparable and critical pairs whose inner mysteries are not yet clear.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 549271
zbMATH Keywords: incomparable pair
zbMATH Keywords: standard example \(S_ n\)
zbMATH Keywords: chevron
zbMATH Keywords: dimension of a poset
zbMATH Keywords: critical pairs
MaRDI profile type: Publication
cites work: Partially Ordered Sets
cites work: Q3291037
cites work: Q5598298
cites work: The 3-Irreducible Partially Ordered Sets
cites work: On the dimension of partially ordered sets
cites work: The rank of a distributive lattice
cites work: Q4004146
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
description: scientific article; zbMATH DE number 549271