Every poset has a central element (Q1068859)

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.