Linear discrepancy of the product of two chains (Q2490422)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Linear discrepancy of the product of two chains
scientific article

    Statements

    Linear discrepancy of the product of two chains (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    2 May 2006
    0 references
    For a partially ordered set \(P=(X,\prec)\), a function \(f: X\;\rightarrow Z\) is isotone on \(P\) if \(f(x)\leq f(y)\) for all \(x,y\in X\) satisfying \(x\prec y\). The linear discrepancy ld\((P)\) of \(P\) is the minimum integer \(l\) such that \(| f(a)-f(b)| \leq l\) for every injective isotone \(f: X\rightarrow Z\) and every pair of incomparable elements \(a,b\) in \(X\). Let \({\mathbf m}\times{\mathbf n}\) be the product of two chains of sizes \(m\) and \(n\), respectively. The authors prove that ld\(({\mathbf m}\times{\mathbf n})=\lceil\frac{mn}{2}\rceil-2\), for \((m,n)\not= (2,2)\) and ld\(({\mathbf 2}\times{\mathbf 2})=1\).
    0 references
    0 references
    linear discrepancy
    0 references
    product of two chains
    0 references

    Identifiers