marriage theorem


Also found in: Wikipedia.

marriage theorem

[′mar·ij ‚thir·əm]
(mathematics)
The proposition that a family of n subsets of a set S with n elements is a system of distinct representatives for S if any k of the subsets, k = 1, 2, …, n, together contain at least k distinct elements. Also known as Hall's theorem.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
Mentioned in ?
References in periodicals archive ?
Notice that by Hall's marriage theorem, the condition on the [J.sub.i]s is equivalent to requiring that (E - [J.sub.1], ..., E - [J.sub.n]) has a system of distinct representatives (SDR); that is, there are [a.sub.1] [member of] E - [J.sub.1], ..., [a.sub.n] [member of] E - [J.sub.n] with [a.sub.i] [not equal to] [a.sub.j] for i = j.
Matroid polytopes and their volumes
We consider the following polyandrous interpretation of Hall marriage theorem. Each cycle of [[sigma].sub.1] will be called a boy and each cycle of [[sigma].sub.2] will be called a girl.
Characters of symmetric groups in terms of free cumulants and Frobenius coordinates

Encyclopedia browser ?
Full browser ?