Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T03:27:06.464Z Has data issue: false hasContentIssue false
  • English
  • Français

The lattice of stable marriages and permutations

Part of: Designs and configurations Lattices

Published online by Cambridge University Press:  09 April 2009

J. S. Hwang
J. S. Hwang
Affiliation:
Department of Mathematical SciencesMcMaster UniversityHamilton, L8S 4K1, Canada
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Recently, we have introduced the notion of stable permutations in a Latin rectangle L(r×c) of r rows and c columns. In this note, we prove that the set of all stable permutations in L (r×c) forms a distributive lattice which is Boolean if and only if c ≤ 2.

Keywords

latticeLatin rectanglestable marriagestable permutationsystem of I-M preferenceand duality principle.

MSC classification

Secondary: 06B05: Structure theory 05B15: Orthogonal arrays, Latin squares, Room squares
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 33 , Issue 3 , December 1982 , pp. 401 - 410
Copyright
Copyright © Australian Mathematical Society 1982

References

[1]Birkhoff, G., Lattice theory, rev. ed. (Amer. Math. Soc., Providence, R. I., 1948).Google Scholar
[2]Gale, D. and Shapley, L. S., ‘College admissions and the stability of marriages’, Amer. Math. Monthly 69 (1962), 9–15.CrossRefGoogle Scholar
[3]Hwang, J. S., ‘Stable permutations in Latin squares’, Soochow J. Math. 4 (1978), 63–72.Google Scholar
[4]Hwang, J. S., ‘On the invariance of stable permutations in Latin rectangles’ Ars Combinatoria, to appear.Google Scholar
[5]Hwang, J. S., ‘Complete stable marriages and system of I-M preferences’, Lecture Notes in Math., Springer-Verlag, Berlin and New York, edited by K. L. McAvaney for 8th Australian Conference 884 (1981), 49–63.Google Scholar
[6]Knuth, D. E., Manages stables et leurs relations avec l'autres problèmes combinatoires (Les Presses de l'Université de Montréal, 1976).Google Scholar