Errata to Mariages Stables (last updated 18 December 2024)

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 52, line 6 propositions chacunes propositions chacun Page 53, line 9 from the bottom à la ville 1 de la ville 1 Page 59, line 5 from the bottom ou elle où elle Page 63, line 2 of the second paragraph hashage hachage Page 65, line 3 from the bottom binômiaux binomiaux Page 67, line 1 peut en fait peut, en fait Page 67, bottom line étant donnée étant donné Page 68, first line of the theorem Etant données des matrices de préférence aléatoire Etant donné des matrices de préférence aléatoires Page 70, line 7 from the bottom étant données étant donné Page 73, line 12 préfère-t-il préfère-t-elle Page 81, line 5 from the bottom et aussi, d’au et celle d’au Page 81, line 4 from the bottom est diminuée sont diminuées Page 83, line 9 from the bottom choix H[X], ont choix H[X] ont Page 84, bottom line O(n^{2}S) O(n^{3}S) Page 88, first line of Corollaire 2 Etant données Etant donné Page 95, line 9 from the bottom x_{ij} = 1 ⇔ x_{ij} = 1 ⇒ Page 97, line 6 donnée une matrice donné une matrice 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.]

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.]

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), 431–442. Reprinted as Chapter 23 of Selected Papers on Analysis of Algorithms. [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.]

Anna R. Karlin, Shayan Oveis Gharan, and Robbie Weber, “A simply exponential upper bound on the maximum number of stable matchings,” arXiv:1711.01032 [cs.DM], 12 pages. [Shows that at most 2^{17n} stable matchings are possible, without attempting to optimize the constants introduced during the proof.]