When linear and weak discrepancy are equal

DOI10.1016/J.DISC.2010.11.003MaRDI QIDQ626763zbMATH OpenOpenAlexFDO

Authors David M. Howard, Stephen J. Young

Publication date 18 February 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2010.11.003

zbMATH Keywords

linear discrepancyweak discrepancy, poset

Mathematics Subject Classification ID

Partial orders, general (06A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

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\).

Recommendations

• Irreducible width 2 posets of linear discrepancy 3
• A characterization of partially ordered sets with linear discrepancy equal to \(2\)
• Simple posets with respect to linear discrepancies
• Linear discrepancy and weak discrepancy of partially ordered sets
• The total linear discrepancy of an ordered set

Cites work

• A characterization of partially ordered sets with linear discrepancy equal to \(2\)
• Can transitive orientation make sandwich problems easier?
• Forbidden subposets for fractional weak discrepancy at most \(k\)
• scientific article; zbMATH DE number 5073478 (Why is no real title available?)
• Intransitive indifference with unequal indifference intervals
• Irreducible width 2 posets of linear discrepancy 3
• Linear discrepancy and bandwidth
• Linear discrepancy and weak discrepancy of partially ordered sets
• On the Weakness of an Ordered Set
• Online linear discrepancy of partially ordered sets
• The fractional weak discrepancy of a partially ordered set

Cited in

(14)

• Linear discrepancy and weak discrepancy of partially ordered sets
• A characterisation of posets that are nearly antichains
• A characterization of partially ordered sets with linear discrepancy equal to \(2\)
• Online linear discrepancy of partially ordered sets
• The total weak discrepancy of a partially ordered set
• Fractional weak discrepancy of posets and certain forbidden configurations
• Enumeration of optimally labelled n-posets of linear discrepancy two
• Simple posets with respect to linear discrepancies
• The fractional weak discrepancy of \((M, 2)\)-free posets
• Linear discrepancy of the complete k-ary tree-poset.
• A note on linear discrepancy and bandwidth
• The \(t\)-discrepancy of a poset
• Irreducible width 2 posets of linear discrepancy 3
• The total linear discrepancy of an ordered set

This page was built for publication: When linear and weak discrepancy are equal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626763)