The order-interval hypergraph of a finite poset and the König property (Q1363653): Difference between revisions

Given a finite poset \((P,\leq)\), if \(\text{I}(P)\) denotes the collection of maximal intervals of \(P\) used as a set of edges the possible multiplicity for pairs of points which are endpoints of elements in \(\text{I}(P)\) produces a hypergraph \(\text{H}(P)= (P,\text{I}(P))\), the order-interval hypergraph of \(P\), which is quite strongly characteristic of its underlying poset \(P\). As in the general setting the indices \(\alpha(\text{H}(P))\), \(\tau(\text{H}(P))\), \(\nu(\text{H}(P))\), \(\rho(\text{H}(P))\) denote the independence number, the point covering number, the matching number and the edge covering number of \(\text{H}(P)\) (and through \(\text{H}(P)\) of \(P\)). Matching pairs of such indices with each other is an interesting and instructive game with a multitude of important results available in the literature for illustration. In this setting, \(\text{H}(P)\) has the König property if \(\nu(\text{H}(P))= \tau(\text{H}(P))\) and the dual König property if \(\alpha(\text{H}(P))= \rho(\text{H}(P))\). If \((P,\leq)\) is an interval order, then the authors show that \(\text{H}(P)\) has both the König property and the dual König property using the interval property constructively in devising an elegant and clever algorithm which runs in polynomial time even though they also show that the general problem of determining these indices is always NP-complete (\(\alpha\) and \(\rho\) earlier, \(\nu\) and \(\tau\) in this paper). The fact that the set of posets \(P\) such that \(\text{H}(P)\) has both König properties is closed under products is proven by an appeal to previous observations and results obtained in this paper and indicates that this property as an ``abstract'' property of ``general posets'' is a viable one and representative of some intriguing kind of symmetry in these posets.