Every poset has a central element
type: Item
instance of: scholarly article
title: Every poset has a central element
zbMATH Open document ID: 0582.06002
DOI: 10.1016/0097-3165(85)90087-1
author: Nathan Linial
author: Michael Saks
published in: Journal of Combinatorial Theory. Series A
publication date: 1985-01-01T00:00:00Z
review text: In this excellent paper the authors answer affirmatively a conjecture which has been open for some years. The authors themselves have asked questions about the complexity of a data location problem and have proved it to boil down to the problem solved here. On the other hand, the complexity of the isomorphism problem for finite distributive lattices also seems to depend on it. Hence, the solution of the authors will have some repercussions in complexity theory. To explain the problem attacked, and solved, in this paper let P denote a finite poset. For any \(x\in P\), we may count the order ideals that x belongs to; set h(x) equal to the fraction of the number of these ideals. Of course, there is always a positive real d such that \(d<h(x)<1-d\). x is then called d-central by the authors. Suppose d can be chosen between 0 and 1/2; then a d-central element will belong to approximately half of the order ideals. Problem: does every finite poset P possess a d-central element for some d, which is independent of P and such that \(0<d<1/2?\) Answer: Yes. d can be chosen as \((1/4)(3-\log_ 25)\approx 0,17\). In an unpublished result J. Shearer has excluded any \(d\gtrsim 0.197\), so the bound given by the authors is not far from best possible. The proof of this deep result can only be sketched. \textit{B. Sands} [Discrete Math. 35, 213-228 (1981; Zbl 0463.06002)] has already proved the main result, albeit for posets of height 1, by using a correspondence between posets and bipartite graphs. The authors extend this correspondence to general posets and show how Sands' proof can be rewritten to make it carry over. This is far from easy and needs some very ingenious weighted averaging, too technical to describe here. As with any good result, the one dealt with in this paper poses new problems, e.g. in the theory of hyperhraphs. They seem to be accessible by the method invented by the authors.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3931070
zbMATH Keywords: isomorphism problem for finite distributive lattices
zbMATH Keywords: complexity theory
zbMATH Keywords: finite poset
zbMATH Keywords: order ideals
zbMATH Keywords: d-central element
zbMATH Keywords: posets of height 1
zbMATH Keywords: bipartite graphs
zbMATH Keywords: hyperhraphs
MaRDI profile type: Publication
full work available at URL: 0097-3165(85)90087-1
OpenAlex ID: W1970716647
cites work: An inequality for the weights of two families of sets, their unions and intersections
cites work: Q3050437
cites work: Q3941433
cites work: Q5331549
cites work: Q3852212
cites work: Q4141872
cites work: Correlation inequalities on some partially ordered sets
cites work: How good is the information theory bound in sorting?
cites work: Information Bounds Are Weak in the Shortest Distance Problem
cites work: The Information-Theoretic Bound is Good for Merging
cites work: Searching ordered structures
cites work: Q3686039
cites work: Counting antichains in finite partially ordered sets
description: scientific article; zbMATH DE number 3931070