§8.6, p. 182 — ν(F) ≤ ν*(F) = τ*(F) ≤ τ(F) for every finite set system

Let $V$ be a finite set and $\mathcal F$ a system of nonempty subsets of $V$. Then the fractional transversal LP and the fractional matching LP of $\mathcal F$ both have optimal solutions $x^*$ and $y^*$, their optimal values agree, and they sit between the matching and transversal numbers:

Here $\tau^*(\mathcal F) = \sum_{v \in V} x^*_v$ is the minimum total weight of a fractional transversal and $\nu^*(\mathcal F) = \sum_{F \in \mathcal F} y^*_F$ the maximum total weight of a fractional matching.

The equality is the linear-programming duality between the two relaxations; it is the step in the proof of Lemma 8.6.3 that turns a bound on fractional matchings of $d$-intervals into a fractional transversal of small weight.

Formalization Note The statement asserts the existence of a fractional transversal $x$ and a fractional matching $y$ such that $x$ is optimal (its objective is $\le$ that of every fractional transversal), $y$ is optimal, and $\nu(\mathcal F) \le \sum_F y_F = \sum_v x_v \le \tau(\mathcal F)$; this is the book's chain with $\tau^*$, $\nu^*$ written as attained optima rather than as possibly empty infima and suprema. The book states the chain "always"; the members of $\mathcal F$ are assumed nonempty, which the book tacitly assumes as well: if $\emptyset \in \mathcal F$ there is no transversal ($\tau$ undefined), the fractional transversal LP is infeasible and the fractional matching LP is unbounded.