Posets with large dimension and relatively few critical pairs
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.
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- scientific article; zbMATH DE number 3172312 (Why is no real title available?)
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 3318595 (Why is no real title available?)
- On the dimension of partially ordered sets
- Partially Ordered Sets
- The 3-Irreducible Partially Ordered Sets
- The rank of a distributive lattice
- Maximal sublattices of finite distributive lattices
- The crossing number of posets
- On the fractional dimension of partially ordered sets
- Dimension, graph and hypergraph coloring
- The graph of critical pairs of a crown
- Standard examples as subposets of posets.
- Forcing posets with large dimension to contain large standard examples
- The proof of the removable pair conjecture for fractional dimension.
- scientific article; zbMATH DE number 6810707 (Why is no real title available?)
- scientific article; zbMATH DE number 867638 (Why is no real title available?)
- Dimension for posets and chromatic number for graphs
- Removing critical pairs
This page was built for publication: Posets with large dimension and relatively few critical pairs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1319081)
