Compactness of Kőnig-property
A hypergraph [math]H=(V,E) [/math] has the Kőnig-property if there is a set [math] \mathcal{D}\subseteq E [/math] of pairwise disjoint hyperedges such that there is a vertex cover consisting of one vertex from each hyperedge in [math] \mathcal{D} [/math]. (Using this terminology, Kőnig's theorem says that every finite bipartite graph has the Kőnig-property). R. Aharoni and N. Bowler conjectured independently the following. If [math]H=(V,E) [/math] is a hypergraph such that all of its hyperedges are finite and for all finite [math] E'\subseteq E [/math] the hypergraph [math] (V,E') [/math] has the Kőnig-property, then [math]H [/math] has the Kőnig-property as well ([1] p. 19. Problem 6.7).
Remarks
One cannot omit the condition that the hyperedges are finite. Consider for example the hypergraph on the natural numbers where the hyperedges are [math] [n,\infty) [/math] for any [math] n [/math]. There are no two disjoint hyperedges but it is impossible to cover the hyperedges by one vertex, although it is possible for any finite subset of edges.
References
- ↑ Directions in infinite graph theory and combinatorics, R. Diestel (editor), North-Holland, 1992. download link