๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The minimum size of critical sets in latin squares

โœ Scribed by Chin-Mei Fu; Hung-Lin Fu; C.A. Rodger

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
224 KB
Volume
62
Category
Article
ISSN
0378-3758

No coin nor oath required. For personal study only.

โœฆ Synopsis

A critical set C of order n is a partial latin square of order n which is uniquely completable to a latin square, and omitting any entry of the partial latin square destroys this property. The size s(C) of a critical set C is the number of filled cells in the partial latin square. The I size of a minimum critical set of order n is s(n). It is likely that s(n) is approximately ~n-, though to date the best-known lower bound is that s(n)>~n + 1. In this paper, we obtain some conditions on C which force s(C)>~ L(n-l)/2J 2. For n > 20, this is used to show that in general s(n)>~ [(7n -3)/6j, thus improving the best-known result.

๐Ÿ“œ SIMILAR VOLUMES

Critical sets in nets and latin squares
Critical sets in nets and latin squares
โœ J.A. Cooper; T.P. McDonough; V.C. Mavron ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 911 KB
A superlinear lower bound for the size o
A superlinear lower bound for the size of a critical set in a latin square
โœ Nicholas J. Cavenagh ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 157 KB ๐Ÿ‘ 1 views

## Abstract A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let __scs__(__n__) denote the smallest possible size of a critical set in a latin square of order __n__. We show that for all __n__, $scs(n)\geq n\lfloo

On the spectrum of critical sets in lati
On the spectrum of critical sets in latin squares of order 2n
โœ Diane Donovan; James LeFevre; G. H. John van Rees ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 197 KB ๐Ÿ‘ 1 views

## Abstract Suppose that __L__ is a latin square of order __m__ and __P__โ€‰โŠ‘โ€‰__L__ is a partial latin square. If __L__ is the only latin square of order __m__ which contains __P__, and no proper subset of __P__ has this property, then __P__ is a __critical set__ of __L__. The critical set spectrum p

On the maximum number of different order
On the maximum number of different ordered pairs of symbols in sets of latin squares
โœ Jeffrey H. Dinitz; Douglas R. Stinson ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 140 KB ๐Ÿ‘ 1 views

## Abstract In this paper, we study the problem of constructing sets of __s__ latin squares of order __m__ such that the average number of different ordered pairs obtained by superimposing two of the __s__ squares in the set is as large as possible. We solve this problem (for all __s__) when __m__

On the size of jump-critical ordered set
On the size of jump-critical ordered sets
โœ M. H. El-Zahar; J. H. Schmerl ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 150 KB

The maximum size of a jump-critical ordered set with jump-number m is at most (m + l)! AMS (MOS) subject classifications (1980). Primary 06AlO; secondary 68C25.