Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A conjecture on the number of SDRs of a (t,n)-family
He D., Lu C. European Journal of Combinatorics33 (1):1-7,2012.Type:Article
Date Reviewed: Jul 9 2012

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.

Reviewer:  Paparao Kavalipati Review #: CR140348 (1211-1163)
Bookmark and Share
  Featured Reviewer  
 
Combinatorics (G.2.1 )
 
 
Counting Problems (G.2.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorics": Date
Applied combinatorics with problem solving
Jackson B., Thoro D., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992. Type: Book (9780201129083)
Feb 1 1993
Parallel generation of permutations and combinations
Chen G., Chern M. BIT 26(3): 277-283, 1986. Type: Article
Jul 1 1988
Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9780387818160)
Jun 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy