Minimal and Maximal Critical Sets in Room Squares
Ghulam Rasool Chaudhry, Jennifer Seberry · Research Online (University of Wollongong) · 1996
In this paper we introduce critical sets in Room squares. We give the cardinality of the minimal critical sets (min. cs) and maximal critical sets (max. cs) for inequivalence classes of Room squares of side 7, 9 and 11. We also describe algorithms to compute min. cs and max. cs and conjecture the lower and upper bounds for min. cs and max. cs. 1 Introduction A number of authors have studied the minimum amount of information needed to recreate combinatorial structures. Critical sets in Latin squares have been studied by (Nelder [15]), (Curran and Van Rees [5]), (Smetaniuk [18]), (Stinson and Van Rees [20]) and (Cooper, Donovon and Seberry [4]). Minimum defining sets of combinatorial designs (see for example [21]) have been studied by Street, Sarvate, Kunkle, Seberry et al. Critical sets have a number of applications in both agriculture and cryptography. This research has been motivated by studies of secret sharing schemes by Cooper et al., key distribution schemes by Merkle (PhD thesi...