we-solve (beta)

Math-2078 · mathematics · Combinatorics

Infinite Lucchesi-Younger

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $D=(V,A)$ be a digraph, possibly infinite and with parallel arcs distinguished. For $X\subseteq V$, write $\delta^+(X)$ and $\delta^-(X)$ for the arcs leaving and entering $X$, respectively. A dicut is a nonempty set $\delta^+(X)$ for which $\delta^-(X)=\varnothing$. A finite dicut has finitely many arcs; its defining vertex set need not be finite.

Does every such digraph admit a family $\mathcal C$ of pairwise arc-disjoint finite dicuts and a choice $a_C\in C$ for each $C\in\mathcal C$ such that \[ F=\{a_C:C\in\mathcal C\} \] meets every finite dicut of $D$? Pairwise disjointness ensures that the chosen representatives are distinct and $|F\cap C|=1$ for each member of the packing. No additional arcs are allowed in $F$.

The hitting requirement ranges over all finite dicuts, including those not in $\mathcal C$. The family and its representative set may both be infinite. If there are no finite dicuts, the empty family and empty set satisfy the requirement.

For finite digraphs this is the packing/transversal conclusion of the Lucchesi--Younger theorem. In the infinite setting an equality of cardinalities alone is weaker than the requested compatible packing and transversal. Neither local finiteness nor countability is assumed, and infinite dicuts are deliberately excluded from the family to be hit.

Short English statement

Can finite directed cuts in every infinite digraph be packed with one representative from each packed cut forming a transversal of all finite directed cuts?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.