Errata to Mariages Stables (last updated 24 November 2023)

Page 39, line 8 from the bottom les femmes y ont apparues les femmes y sont apparues Page 51, line 3 −(n − m)/m −(n − m)/n Page 53, line 9 from the bottom à la ville 1 de la ville 1 Page 63, line 2 of the second paragraph hashage hachage Page 68, first line of the theorem aléatoire aléatoires Page 84, bottom line O(n^{2}S) O(n^{3}S) Page 95, line 9 from the bottom x_{ij} = 1 ⇔ x_{ij} = 1 ⇒ Page 97, line 15 polynômial polynomial Page 99, solution 1.2 Ee.) Ee). Page 102, line 7 1–4. 1–5. Page 102, line 9 1959 1969 Page 102, line 12 connection connexion

Additional comments and references — stated in English: Page 84, bottom [An improved algorithm that requires only O(n^{2} + nS) steps was subsequently published by Dan Gusfield, SIAM Journal on Computing 16 (1987), 111–128.] Page 103, bottom Dan Gusfield and Robert W. Irving, The Stable Marriage Problem (Cambridge, Massachusetts: MIT Press, 1989). [The theory of stable marriages has advanced greatly since these lectures were first presented, and significant new results continue to be discovered. This book presents an excellent summary of what was known in 1989, including the status of the 12 research problems of Lecture 7.]

Akihisa Tamura, “Transformation from arbitrary matchings to stable matchings,” Journal of Combinatorial Theory (A) 62 (1993), 310–323. [Negative answer to Problem 8: Stability cannot always be achieved by a sequence of divorces.]

Fred Galvin, “The list chromatic index of a bipartite multigraph,” Journal of Combinatorial Theory (B) 63 (1995), 153–158. [Uses the theory of stable marriages to resolve a famous conjecture of J. Dinitz.]

Donald E. Knuth, “An exact analysis of stable allocation,” Journal of Algorithms 20 (1996), to appear. [A related problem of matching traders to indivisible goods leads to interesting new relations between permutations. This paper includes further information about research problem 2, which remains the most fascinating unsolved problem about the fundamental algorithm for stable marriages.]

Tomás Feder, Stable Networks and Product Graphs, Memoirs Amer. Math. Soc. 555 (1995), 223 pp. [This comprehensive monograph places the theory of stable marriage in the more general mathematical context of stable configurations in networks. Many elegant results are obtained, including new algorithms that yield solutions symmetrical with respect to men and women. For example, one can find a “minimum regret” stable marriage, in which the rank of the least favorable partner is as small as possible, in O(n^{2}) steps; one can find an “egalitarian” stable marriage, in which the sum of ranks of all partners in minimized, in O(n^{3}) steps.]