Optimal representations of partially ordered sets and a limit Sperner theorem
type: Item
instance of: scholarly article
title: Optimal representations of partially ordered sets and a limit Sperner theorem
zbMATH Open document ID: 0651.05014
DOI: 10.1016/S0195-6698(86)80003-8
author: Konrad Engel
published in: European Journal of Combinatorics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 4061252
zbMATH Keywords: weighted partially ordered
zbMATH Keywords: variance
zbMATH Keywords: Optimal representations
zbMATH Keywords: Sperner theory
zbMATH Keywords: asymptotic formula
MaRDI profile type: Publication
cites work: An inequality for the weights of two families of sets, their unions and intersections
cites work: Q4044544
cites work: Q4055670
cites work: Q3673576
cites work: Q3768943
cites work: Q3314640
cites work: An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
cites work: A new proof of a theorem of Harper on the Sperner-Erdős problem
cites work: Q5514188
cites work: Q3260832
cites work: Some Results on Matching in Bipartite Graphs
cites work: Q4196436
cites work: Q3344243
cites work: The morphology of partially ordered sets
cites work: The global theory of flows in networks
cites work: Q3236252
cites work: Normalized Matching in Direct Products of Partial Orders
cites work: Maximal sized antichains in partial orders
cites work: Q4133393
cites work: Product partial orders with the Sperner property
cites work: Q5618791
cites work: Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
full work available at URL: s0195-6698(86)80003-8
OpenAlex ID: W2089062952
description: scientific article; zbMATH DE number 4061252