Network Flow and Systems of Representatives

../

common_sdr: Specializes the common-multiset theorem to injective representatives for both families.

definitions: Fixes finite indexed families, shared multisets and integer occurrence bounds.

external_inputs: Separates max-flow and integrality inputs from the paper’s complete representative reductions.

hall_flow: Reconstructs the distinct network-flow proof of finite Hall representatives.

identical_families: Preserves O. Gross’s separate union–intersection deduction for identical families.

prescribed_representatives: Extracts the mandatory-element specialization with both necessary inequalities retained.

theorem_1: Proves the exact lower and upper multiplicity tests using two classes of cuts.

theorem_2: Expands the paper’s common-multiset network and every cut calculation omitted there.

---

L. R. Ford, Jr. and D. R. Fulkerson, Network Flow and Systems of Representatives, Canadian Journal of Mathematics 10 (1958), 78–84. DOI. Published scan. Source record.

The copy read for this card is the seven-page Cambridge scan of the published article. The paper records receipt on 18 March 1957. Cambridge's 20 November 2018 online date is a digitization date, not a later mathematical version. No second version is asserted. The article prints no copyright notice of its own; the publisher's article page shows "Copyright © Canadian Mathematical Society 1958" and names no Creative Commons license (https://www.cambridge.org/core/product/identifier/S0008414X00045168/type/journal_article, read 2026-10-02), every other right reserved.

The paper turns representative assignments into integral flows and then reads existence conditions from cuts. The library retains its network proof of finite Hall, one-family multiplicity theorem, mandatory-element specialization, common-multiset theorem, O. Gross's identical-family deduction, and common-SDR corollary. These six complete local or relative arguments preserve distinct methods and useful specializations. In particular, the full cut calculation left to the reader in Section 3 is supplied.

The definitions make finite indexing, integer bounds and common multiplicities explicit. The common assignments may use different index orders. Max-flow/min-cut and integrality are theorem inputs to these 1958 deductions. A complete 1957 constructive proof is available for their terminal-direction convention. Finite capacities replace infinity exactly in these bounded acyclic networks. The source's assignment-specific flow formula and an incidence subscript are clarified on the relevant pages; these local clarifications are not author-issued errata.

The flow-Hall method differs from Hall's original 1935 proof. It provides background for the distinct network and matroid methods in Edmonds–Fulkerson (1965). The paper's introductory pointers to broader partition quotas and reductions back to Hall remain pointers unless their separate arguments are compiled. No numbered Erdős status change, formal proof build, checked program or current priority claim follows from this source alone.

The prescribed-multiplicity extension is Welsh (1969), Theorem 12. When every $p_i=q_i=1$, its total is $N=n$ and its intersection condition rearranges exactly to the common-SDR criterion above. The Welsh source keeps its finite Rado input explicit; this reciprocal link does not merge the two papers' proof routes.

Results.

• Hall's theorem by flows (Section 2, pp. 80–81, equations (2)–(6)): an SDR exists exactly when every $k$ of the sets have at least $k$ elements in their union.
• Theorem 1 (p. 82): an SRR exists exactly when $|X|\le\min\{n-\sum_i\alpha_i+\alpha(I(X)),\ \beta(I(X))\}$ for every subset $X$ of the indices, where $I(X)$ indexes the elements of $\bigcup_{j\in X}S_j$.
• The Hoffman–Kuhn specialization (p. 82): an SDR containing prescribed elements $a_1,\ldots,a_q$.
• Theorem 2 (p. 83): the criterion (12) for a common SRR of two families, whose network is given on p. 82 and whose proof the paper leaves to the reader.
• The deduction after Theorem 2 (p. 83): (12) implies (11) for $\mathcal S$ (the page adds the symmetric case for $\mathcal T$), and (11) implies (12) when $S_i=T_i$ for all $i$; the paper's footnote credits the short proof of this converse to O. Gross.
• Corollary (p. 83): a common SDR exists exactly when $|X|+|Y|\le n+|I(X)\cap I(Y)|$ for all $X,Y\subseteq\{1,\ldots,n\}$, equation (13), where $I(Y)$ indexes the elements of $\bigcup_{j\in Y}T_j$.

Bears on. No Erdős problem: the paper states no relation to a numbered Erdős problem, and none of its results is recorded as bearing on one.

Read status: claims checked. All seven printed pages, 78–84, were read on the page images; the statements on the result pages were checked clause by clause against them. The proofs on the result pages are the library's own reconstructions, and nothing is independently reviewed.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.