Concerning the maximum number of stable matchings in the stable marriage problem
type: Item
instance of: scholarly article
title: Concerning the maximum number of stable matchings in the stable marriage problem
zbMATH Open document ID: 0997.05002
DOI: 10.1016/S0012-365X(01)00194-7
author: Edward G. Thurber
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: Let us take \(n\) men and \(n\) women. Each man ranks the women in order of preference from \(1\) to \(n\). Similarly, each woman ranks the men in order of preference form \(1\) and \(n\). A matching consists of \(n\) ordered pairs \((i_r,j_r)\) where \(i_r\) is in the set of men, \(j_r\) is in the set of women. A matching is stable if it does not contain a man \(i_s\) and a woman \(j_t\) where \(i_s\) prefers \(j_t\) to \(j_s\) and \(j_t\) prefers \(i_s\) to \(i_t\). The function \(f(n)\) denotes the number of stable matchings possible in an instance of size \(n\). The author proves that \(f(n)\) is strictly increasing, and derives lower bounds for \(f(n)\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1746260
zbMATH Keywords: stable marriage
zbMATH Keywords: matching
reviewed by: R. G. Stanton
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1746260