Given a family of sets, it is an interesting exercise to choose a distinct element from each set so that a meaningful pattern can emerge from the selection. Such problems arise, for example, in constructing Latin squares, and in the popular puzzle of arranging eight nonattacking queens on a chessboard.
A system of distinct representative elements (a set with certain properties) is called an SDR, and several SDRs are possible for a given family. It can be shown using counting arguments that whenever any union of k sets in a family has at least k elements, then an SDR must exist for the family.
However, finding the minimum number of possible SDRs has not been completely addressed, though certain cases have been solved. The authors of this paper provide a proof for an open conjecture.
The paper defines a (t,n)-family and restates Hall’s theorem in more general terms. The authors provide relevant notation and describe the conjecture by Chang. According to the authors, an earlier attempt at proving the minimum number of possible SDRs had a mistake.
This paper derives a more general result. Introducing a (t,n; a1, a2, .. an)-family, the authors show a proof for the number of SDRs for such families. Since a (t,n)-family happens to be special case, in fact a (t,n; 1, 1, .. 1)-family, from the stronger proof, Chang’s conjecture follows as a corollary.
The paper is very well written and includes relevant introductory material. The proofs are fun to read, but require some mathematical background.