Optimal representations of partially ordered sets and a limit Sperner theorem

Let (P,v) be a finite, probabilistically weighted partially ordered set, i.e. v is a function \(P\to {\mathbb{R}}_+\setminus \{0\}\) such that \(\sum_{x\in P}v(x)=1\). A representation of (P,v) is a function x: \(P\to {\mathbb{R}}\) such that x(p)-x(p')\(\geq 1\) if \(p>p'\), for all p,p'\(\in P\). The variance \(\sigma^ 2_ x\) of a representation x is defined by \(\sigma^ 2_ x=\sum_{p\in P}v(p)x(p))^ 2\), and the variance \(\sigma^ 2(P,v)\) of the poset (P,v) is the infimum of the variances of all representations of (P,v). Optimal representations of (P,v), i.e. such representations x for which \(\sigma^ 2_ x=\sigma^ 2(P,v)\), are studied. Thereby quadratic programming, linear programming and flow methods are used. Connections to well-known results in the Sperner theory are discussed. At last an asymptotic formula including \(\sigma\) (P,v) is given for the maximum weight of an antichain in a product of n factors (P,v), where n tends to infinity.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Optimal representations of partially ordered sets and a limit Sperner theorem

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