Systems of Distinct Representatives

Choosing Distinct Elements from a Family of Sets

Suppose several people each list the objects they are willing to receive, or several tasks each have a set of eligible workers. A selection is successful if each person or task gets one eligible object or worker, and no object or worker is used twice. The mathematical object that records such a selection is a system of distinct representatives. The word “representative” refers to a chosen element of a set; it does not mean choosing one of the sets themselves.

It is useful to index the sets, even when some of them are equal. The indices record how many separate choices must be made. For example, two different people may have exactly the same list of acceptable objects: their lists are equal as sets, but they still require two representatives.

Definition: Let \(I\) be a finite index set and let \((A_i)_{i\in I}\) be a family of sets. A system of distinct representatives, or SDR, is a family of elements \((x_i)_{i\in I}\) such that \(x_i\in A_i\) for every \(i\in I\), and \(x_i\ne x_j\) whenever \(i\ne j\). The elements \(x_i\) are the representatives; the sets \(A_i\) are the sets being represented.

The representatives need not be elements of the index set \(I\). They come from the sets \(A_i\), which may be different from \(I\). The sets need not be disjoint, and they need not be different from one another. If \(I\) is empty, the empty choice is an SDR: there are no membership or distinctness conditions to violate. If \(I\) is nonempty and some \(A_i\) is empty, no SDR exists, because no element can be chosen from that set.

Representatives as an Injective Choice

An SDR can be recorded as a function: it assigns to each index \(i\) its chosen element \(x_i\). The requirement that representatives be distinct says exactly that this function is injective. This viewpoint separates the role of an index from the role of the element chosen for it.

Proposition: The family \((A_i)_{i\in I}\) has an SDR if and only if there is an injective function \(f:I\to\bigcup_{i\in I}A_i\) satisfying \(f(i)\in A_i\) for every \(i\in I\). For \(I=\varnothing\), the union is understood to be empty and the empty function has these properties.

Proof. Suppose \((x_i)_{i\in I}\) is an SDR. Define \(f(i)=x_i\) for each \(i\in I\). The definition of an SDR gives \(f(i)\in A_i\), so \(f(i)\in\bigcup_{j\in I}A_j\). It also gives \(f(i)\ne f(j)\) whenever \(i\ne j\), so \(f\) is injective. Conversely, suppose such an injective function \(f\) is given. Set \(x_i=f(i)\). Then \(x_i\in A_i\) for each \(i\), and injectivity gives \(x_i\ne x_j\) for distinct indices. Thus \((x_i)_{i\in I}\) is an SDR. When \(I\) is empty, both statements hold for the empty family and empty function, so the equivalence also covers that case. \(\square\)

Worked Example: Assigning Three Different Materials

Suppose three projects have available materials given by \(A_1=\{a,b\}\), \(A_2=\{a,c\}\), and \(A_3=\{b,c\}\). We seek one material for each project, with no material assigned twice.

Choose \(x_1=b\), \(x_2=a\), and \(x_3=c\). Membership checks give \(b\in A_1\), \(a\in A_2\), and \(c\in A_3\). The chosen elements \(b,a,c\) are pairwise distinct, so these choices form an SDR. In function notation, \(f(1)=b\), \(f(2)=a\), and \(f(3)=c\); the function is injective.

For an independent check, the union of the sets is \(\{a,b,c\}\), and the three choices use each of its elements exactly once. Notice that the indices \(1,2,3\) identify the projects, while \(a,b,c\) are the representatives. Choosing the indices would not solve the material-assignment problem.

The Incidence Graph Records the Choices

A bipartite graph gives a compact way to record which elements are available to which indices. Its left vertices represent the sets, and its right vertices represent the possible representatives. An edge records membership. This construction is called an incidence graph for the indexed family. Here the left and right copies of the vertices are treated as separate, even if the same symbol happens to appear as an index and as an element.

Definition: For a finite indexed family \((A_i)_{i\in I}\), its incidence graph is the bipartite graph \(G=(L\cup R,E)\), where \(L=\{L_i:i\in I\}\) is a copy of the index set, \(R=\{R_x:x\in\bigcup_{i\in I}A_i\}\) is a separate copy of the union of the sets, and \(L_iR_x\in E\) exactly when \(x\in A_i\). A matching is a set of edges no two of which share an endpoint. A matching saturates \(L\) if every vertex in \(L\) is incident with one of its edges.

Theorem: A finite indexed family of sets has an SDR if and only if its incidence graph has a matching that saturates every left vertex.

Proof. Suppose first that \((x_i)_{i\in I}\) is an SDR. For each \(i\in I\), include the edge \(L_iR_{x_i}\). It is an edge because \(x_i\in A_i\). Every left vertex \(L_i\) is incident with its selected edge, so all left vertices are saturated. If two selected edges shared a right endpoint, then \(x_i=x_j\) for two different indices \(i,j\), contrary to the distinctness of the representatives. Edges from different indices also have different left endpoints. Thus the selected edges form a matching. Conversely, suppose a matching saturating \(L\) is given. Each \(L_i\) is incident with exactly one matching edge, say \(L_iR_{x_i}\). By the definition of the incidence graph, \(x_i\in A_i\). Since the edges form a matching, no two of them share a right endpoint, so \(x_i\ne x_j\) for different indices. Hence \((x_i)_{i\in I}\) is an SDR. If \(I=\varnothing\), the incidence graph has no left vertices, the empty matching saturates \(L\), and the empty family is an SDR. \(\square\)

This result translates between two descriptions of the same selection: a representative system lists the chosen elements, while a matching lists the corresponding membership edges. It does not, by itself, guarantee that an SDR exists; it tells us precisely what kind of matching would encode one.

Worked Example: Choosing Distinct Days

Three activities have available days \(A_1=\{\text{Mon},\text{Tue}\}\), \(A_2=\{\text{Tue}\}\), and \(A_3=\{\text{Wed},\text{Thu}\}\). The index \(i\) identifies an activity, while a day is a possible representative.

The incidence graph has vertex sets \(L=\{L_1,L_2,L_3\}\) and \(R=\{R_{\text{Mon}},R_{\text{Tue}},R_{\text{Wed}},R_{\text{Thu}}\}\). Its edge set is \(E=\{L_1R_{\text{Mon}},L_1R_{\text{Tue}},L_2R_{\text{Tue}},L_3R_{\text{Wed}},L_3R_{\text{Thu}}\}\). The edges record exactly the stated memberships.

Since \(A_2\) contains only Tue, activity 2 must receive Tue if an SDR is to exist. Then activity 1 cannot receive Tue, so choose Mon for activity 1. Choose Wed for activity 3. The resulting representatives are \(x_1=\text{Mon}\), \(x_2=\text{Tue}\), and \(x_3=\text{Wed}\).

In the incidence graph these choices are the edges \(L_1R_{\text{Mon}}\), \(L_2R_{\text{Tue}}\), and \(L_3R_{\text{Wed}}\). They share no endpoints and meet every left vertex, so they form a matching saturating \(L\). Checking directly, Mon belongs to \(A_1\), Tue belongs to \(A_2\), Wed belongs to \(A_3\), and the three days are distinct.

Worked Example: Two Sets That Are Equal Still Need Two Choices

Let \(A_1=\{p,q\}\), \(A_2=\{p,q\}\), and \(A_3=\{q,r\}\). Although \(A_1=A_2\) as sets, the indices 1 and 2 represent two separate choices. We need three distinct elements, not merely one representative for each different set that appears.

The incidence graph is \(G=(L\cup R,E)\), where \(L=\{L_1,L_2,L_3\}\), \(R=\{R_p,R_q,R_r\}\), and \(E=\{L_1R_p,L_1R_q,L_2R_p,L_2R_q,L_3R_q,L_3R_r\}\). Choose \(x_1=p\), \(x_2=q\), and \(x_3=r\). Each choice belongs to its indexed set, and \(p,q,r\) are pairwise distinct. Thus these choices form an SDR, represented by the matching \(\{L_1R_p,L_2R_q,L_3R_r\}\).

Check: the selected matching has three edges, one incident with each of the three left vertices, and its right endpoints are the three different vertices \(R_p,R_q,R_r\). This verifies both the assignment and the distinctness requirement.

When a Distinct Representative System Cannot Exist

An SDR can fail because some set has no available element, or because several indices have too few different elements available among their sets. The second issue is not fixed by repeatedly choosing an element that works for just one set: the choices must be coordinated so that no representative is used twice. For small families, the definition itself gives a direct way to check failure by examining the available choices.

Worked Example: Two Activities Compete for One Day

Let \(A_1=\{\text{Tue},\text{Wed}\}\), \(A_2=\{\text{Tue}\}\), and \(A_3=\{\text{Tue}\}\). We ask whether all three indices can receive distinct representatives. The incidence graph is \(G=(L\cup R,E)\), where \(L=\{L_1,L_2,L_3\}\), \(R=\{R_{\text{Tue}},R_{\text{Wed}}\}\), and \(E=\{L_1R_{\text{Tue}},L_1R_{\text{Wed}},L_2R_{\text{Tue}},L_3R_{\text{Tue}}\}\).

Both \(A_2\) and \(A_3\) contain only Tue. Therefore any choice meeting the membership requirement for index 2 has \(x_2=\text{Tue}\), and any such choice for index 3 has \(x_3=\text{Tue}\). These representatives are equal, so they cannot both belong to an SDR. The graph gives the same obstruction: \(L_2\) and \(L_3\) are both adjacent only to \(R_{\text{Tue}}\), so a matching cannot contain an edge incident with each of \(L_2,L_3\).

A partial choice is possible: \(x_1=\text{Wed}\) and \(x_2=\text{Tue}\) are distinct and valid. But index 3 would still have to use Tue, already chosen for index 2. Thus a matching covering some left vertices is not enough; the theorem requires a matching that saturates every left vertex.

Common Mistake: Confusing the Sets with Their Representatives

Suppose \(A_1=\{a,b\}\) and \(A_2=\{a,c\}\). A mistaken argument might say, “The sets \(A_1\) and \(A_2\) are different, so they are distinct representatives.” This does not meet the definition: the representatives must be elements of the sets, not the sets themselves. The sets are not choices from their own union in this example; the required choices must be elements such as \(a,b,c\).

A correct selection is \(x_1=b\) and \(x_2=a\). The membership checks are \(b\in A_1\) and \(a\in A_2\), and the distinctness check is \(b\ne a\). In the incidence graph, these are the edges \(L_1R_b\) and \(L_2R_a\), which have no common endpoint. This correction makes both requirements explicit: each representative must be allowed for its index, and different indices must receive different elements.

Systems of distinct representatives are useful whenever a problem asks for one eligible object per requirement without reusing an object. Their incidence graphs let us use the language of matchings to describe those assignments. The key discipline is to preserve the indices: equal sets still represent separate requirements, and an SDR must provide one element for every index.

Check Your Understanding

For each question, distinguish the indices, the sets, and the possible representatives.

Let \(A_1=\{u,v\}\), \(A_2=\{v,w\}\), and \(A_3=\{u,w\}\). Give an SDR and state its three representatives.
If \(A_1=A_2=\{a,b\}\), does equality of the sets prevent an SDR for the two indices? Explain.
Write the vertex sets and edge set of the incidence graph for \(A_1=\{r,s\}\) and \(A_2=\{s\}\).
Prove directly from the definition that a family with an empty member has no SDR.
In the incidence-graph theorem, explain why a matching that fails to saturate one left vertex cannot encode an SDR for the whole indexed family.