The order-interval hypergraph of a finite poset and the König property
type: Item
instance of: scholarly article
title: The order-interval hypergraph of a finite poset and the König property
zbMATH Open document ID: 0880.05067
DOI: 10.1016/0012-365X(95)00356-2
author: Isma Bouchemakh
author: Konrad Engel
published in: Discrete Mathematics
publication date: 1997-09-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1047046
zbMATH Keywords: finite poset
zbMATH Keywords: intervals
zbMATH Keywords: hypergraph
zbMATH Keywords: independence number
zbMATH Keywords: point covering number
zbMATH Keywords: matching number
zbMATH Keywords: edge covering number
zbMATH Keywords: König property
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q4099676
cites work: Interval stability and interval covering property in finite posets
cites work: Q3347930
cites work: Q3797242
cites work: Betweenness, orders and interval graphs
cites work: Strong versions of Sperner's theorem
cites work: Q3686754
cites work: On the structure of the lattice of noncrossing partitions
cites work: Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
cites work: Q3202956
cites work: A linear-time algorithm for edge-disjoint paths in planar graphs
cites work: Interval packing and covering in the Boolean lattice
full work available at URL: 0012-365x(95)00356-2
OpenAlex ID: W2014669583
Recommended article: Q5703162
Recommended article: On the Dual König Property of the Order-interval Hypergraph of Two Classes of N-free Posets
Recommended article: Q4433501
Recommended article: Interval \(k\)-graphs and orders
Recommended article: Combinatorial aspects of interval orders and interval graphs
Recommended article: On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
Recommended article: On the chromatic number of order-interval hypergraphs
Recommended article: The interval order polytope of a digraph
Recommended article: The poset of graphs ordered by induced containment
Recommended article: Exchangeable interval hypergraphs and limits of ordered discrete structures
description: scientific article; zbMATH DE number 1047046