Infinite Lucchesi-Younger

From Egres Open
Jump to: navigation, search

For a digraph [math] D=(V,A) [/math], we call a nonempty [math] C\subseteq A [/math] a dicut if there is some [math] X\subseteq V [/math] such that no edge enters [math] X [/math] and [math] C [/math] consists of the outgoing edges of [math] X [/math]. The conjecture states that for any [math] D [/math], there exists a system [math] \mathcal{C} [/math] of pairwise disjoint finite dicuts and an edge set [math] F\subseteq A [/math] consisting of one edge from each element of [math] \mathcal{C} [/math], such that [math]F[/math] intersects every finite dicut of [math] D [/math].


Remarks

The conjecture was proposed by R. Aharoni and K. Heuer independently. One cannot omit the condition that the dicuts are finite. Consider for example the digraph on the natural numbers in which [math] mn [/math] is an edge iff [math] m \lt n [/math]. Then there are no two disjoint dicuts but it is impossible to cover the dicuts by one edge. The Lucchesi-Younger theorem states that the conjecture holds for finite digraphs. Furthermore, it holds for digraphs where any edge is an element of at most finitely many finite dicuts. By applying the finite theorem and using compactness arguments, one can show that the conjecture is implied by the conjecture Compactness of Kőnig-property.