ICS 269, Fall 2022: Theory Seminar
Bren Hall 1427, 1:00 – 1:50

28 October 2022

Concerning the maximum number of stable matchings in the stable marriage problem

Rohith Gangam

Abstract: The function, f(n), represents the maximum number of stable matchings possible in an instance of size n of the stable marriage problem. It is shown that f(n) is a strictly increasing function of n, and a result of Knuth’s concerning the exponential growth of this function is generalized to all positive integers, n. A method for constructing ranking matrices is used to produce instances with many stable matchings. A subproblem of the stable marriage problem developed by Eilers, called the pseudo-Latin marriage problem, plays a significant role as a tool and as motivation in the paper.

Link: https://core.ac.uk/download/pdf/82220141.pdf by Edward G. Thurber