Problems of order optimization (Q5960195)

In the introduction, different results concerning the investigation of monotone Boolean functions are presented, and it is mentioned that the aim of this paper is a restatement of a class of combinatorial problems in terms of the order optimization on finite partially ordered sets. The main definitions and the statement of the studied problems are presented in Section 2. In Section 3 the problem of order optimization on the Boolean cube is presented. In the set of all extensions of the natural order relation, the inductive order relation \(\leq_i\), the layered inductive order relation \(\leq_s\) and the canonical order relation \(\leq_c\) are considered. For those relations the following order of inclusions holds: \(\leq\subset\leq_c\subset\leq_s\subset\leq_i\). In the theorems 1-5, the relations that hold for the Shannon function \(\varphi(n)\) of different problems concerning the monotone Boolean functions are given. In Section 4 the problem of order optimization of a finite-valued \(n\)-dimensional lattice is considered, and some relations concerning the Shannon function of different problems are proved. In Section 5 the canonical order \(M(n)\) is considered, and a relation that holds for the Shannon function of order optimization with an oracle on the lattice \(M(n)\) is proved. The distributive lattice generated by the set of all \(n\)-element sets ordered in nondecreasing order is considered in Section 6, and a relation for the Shannon function of the order optimization with an oracle is proved.