System of distinct representatives 2026-10-14
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.