\font\tenbxsl=cmbxsl10
\centerline{\bf Errata to \tenbxsl Mariages Stables}
\centerline{\sl (last updated 18 December 2024)}

\font\manfnt=manfnt
\advance\medskipamount -1pt
\def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change
\def\bugonpage #1, #2:
  {\medbreak\noindent{\bf Page #1, }#2\par\nobreak\smallskip\noindent}

\bugonpage 39, line 8 from the bottom:
les femmes y ont apparues \becomes les femmes y sont apparues

\bugonpage 51, line 3:
$-(n-m)/m$ \becomes $-(n-m)/n$

\bugonpage 52, line 6:
propositions chacunes \becomes propositions chacun

\bugonpage 53, line 9 from the bottom:
\`a la ville 1 \becomes de la ville 1

\bugonpage 59, line 5 from the bottom:
ou elle \becomes o\`u elle

\bugonpage 63, line 2 of the second paragraph:
{\it hashage \becomes hachage}

\bugonpage 65, line 3 from the bottom:
bin\^omiaux \becomes binomiaux

\bugonpage 67, line 1:
peut en fait \becomes peut, en fait

\bugonpage 67, bottom line:
\'etant donn\'ee \becomes \'etant donn\'e

\bugonpage 68, first line of the theorem:
Etant donn\'ees des matrices de pr\'ef\'erence al\'eatoire \becomes 
Etant donn\'e des matrices de pr\'ef\'erence al\'eatoires

\bugonpage 70, line 7 from the bottom:
\'etant donn\'ees \becomes \'etant donn\'e

\bugonpage 73, line 12:
pr\'ef\`ere-t-il \becomes pr\'ef\`ere-t-elle

\bugonpage 81, line 5 from the bottom:
et aussi, d'au \becomes et celle d'au

\bugonpage 81, line 4 from the bottom:
est diminu\'ee \becomes sont diminu\'ees

\bugonpage 83, line 9 from the bottom:
choix $H[X]$, ont \becomes choix $H[X]$ ont

\bugonpage 84, bottom line:
$O(n^2S)$ \becomes $O(n^3S)$

\bugonpage 88, first line of Corollaire 2:
Etant donn\'ees \becomes Etant donn\'e

\bugonpage 95, line 9 from the bottom:
$x_{ij}=1\Leftrightarrow$ \becomes $x_{ij}=1\Rightarrow$

\bugonpage 97, line 6:
donn\'ee une matrice \becomes donn\'e une matrice

\bugonpage 97, line 15:
polyn\^omial \becomes polynomial

\bugonpage 99, solution 1.2:
$Ee.)$ \becomes $Ee)$.

\bugonpage 102, line 7:
1--4. \becomes 1--5.

\bugonpage 102, line 9:
1959 \becomes 1969

\bugonpage 102, line 12:
connection \becomes connexion

\vfill\eject
\leftline{\bf Additional comments and references --- stated in English:}
\parindent=0pt

\bugonpage 84, bottom:
[An improved algorithm that requires only $O(n^2+nS)$ steps was subsequently
published by Dan Gusfield, {\sl SIAM Journal on Computing\/ \bf16} (1987),
111--128.]

\font\tencsc=cmcsc10
\bugonpage 103, bottom:
{\tencsc Dan Gusfield} and {\tencsc Robert W. Irving}, {\sl The Stable
Marriage Problem\/} (Cambridge, Massachusetts: MIT Press, 1989).
\smallskip
[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.]

\medskip
{\tencsc Akihisa Tamura}, ``Transformation from arbitrary matchings to stable
matchings,'' {\sl Journal of Combinatorial Theory\/} (A) {\bf62} (1993),
310--323.
\smallskip
[Negative answer to Problem 8: Stability cannot always be achieved by a
sequence of divorces.]

\medskip
{\tencsc Tom\'as Feder}, {\sl Stable Networks and Product Graphs}, Memoirs
Amer.\ Math.\ Soc.\ {\bf555} (1995), 223~pp.
\smallskip
[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.]

\medskip
{\tencsc Fred Galvin}, ``The list chromatic index of a bipartite multigraph,''
{\sl Journal of Combinatorial Theory\/} (B) {\bf63} (1995), 153--158.
\smallskip
[Uses the theory of stable marriages to resolve a famous conjecture of
J.~Dinitz.]

\medskip
{\tencsc Donald E. Knuth}, ``An exact analysis of stable allocation,''
{\sl Journal of Algorithms\/ \bf20} (1996), 431--442.
Reprinted as Chapter~23 of {\sl Selected Papers on Analysis of Algorithms}.

\smallskip
[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.]

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

\bye

