A characterization of partially ordered sets with linear discrepancy equal to \(2\) (Q2464732): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s11083-007-9065-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2166855446 / rank | |||
Normal rank |
Revision as of 03:31, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of partially ordered sets with linear discrepancy equal to \(2\) |
scientific article |
Statements
A characterization of partially ordered sets with linear discrepancy equal to \(2\) (English)
0 references
17 December 2007
0 references
The linear discrepancy of a poset \((P,\leq )\) is the least natural number \(k\) such that there is a linear extension \(L\) of \(P\) such that if \(x\) and \(y\) are incomparable in \(P,\) then \(\left| h_{L}(x)-h_{L}(y)\right| \leq k\), where \(h_{L}(x)\) is the height of \(x\) in \(L.\) In this paper the authors characterize the posets of linear discrepancy \(2\) and show that this problem is equivalent to finding the posets with linear discrepancy equal to \(3\) having the property that the deletion of any point results in a reduction in the linear discrepancy. They complete the forbidden subposet characterization of posets with linear discrepancy equal to \(2\) by finding the minimal posets of width \(3\) with linear discrepancy equal to \(3.\)
0 references
poset
0 references
linear discrepancy
0 references
linear extension
0 references