When linear and weak discrepancy are equal (Q626763)

For a poset \(P\), let \(\mathcal O(P)\) be the collection of order-preserving maps from \(P\) to \(\mathbb N\), let \(\mathcal I(P)\) be the collection of injective order-preserving maps from \(P\) to \(\mathbb N\), and let \(\mathcal F(P)\) be the collection of fractional order-preserving maps from \(P\) to \(\mathbb Q\). The linear discrepancy of \(P\), denoted by \(\text{ld}(P)\), is \(\min\, \max_{f\in \mathcal I(P), \, x||y} |f(x)-f(y)|\), where \(x||y\) means that \(x\) is incomparable to \(y\) in \(P\). The weak discrepancy of \(P\), denoted by \(\text{wd}(P)\), is \(\min\, \max_{f\in \mathcal O(P), \, x||y} |f(x)-f(y)|\), and the fractional weak discrepancy of \(P\), denoted by \(\text{wd}_{\text f}(P)\), is \(\min\, \max_{f\in \mathcal F(P), \, x||y} |f(x)-f(y)|\). Clearly, \(\text{wd}_{\text f}(P)\leq \text{wd}(P) \leq \text{ld}(P)\). The paper under review shows that determining whether \(\text{ld}(P)=\text{wd}(P)\) is NP-complete. Let \(\mathcal W_d\) be the collection of \(d\)-weak-discrepancy-irreducible posets where there exists a maximal forcing cycle with all the up steps consecutive. It is shown that if \(P\) is a poset with \(\text{ld}(P)=d\), then \(\text{wd}(P)=d\) if and only if there exists a subposet \(W\) of \(P\) such that \(W\in \mathcal W_d\).