System of distinct representatives

ID: system-of-distinct-representatives

A system of distinct representatives for a finite indexed family of finite sets chooses one element per index, with all choices distinct. Form a bipartite graph with left vertex set , right vertex set , and edges whenever . Matching saturation of is precisely a system of distinct representatives. Hence Hall's marriage theorem says that such choices exist exactly when for every subset . Repeated equal sets still have separate indices and separate demands.

New to topics? Read the docs here!