当前位置： 文档下载 > 所有分类 > Disjoint critical sets in latin squaresABSTRACT: A critical set in a Latin square is a subset of the Latin square containing just enough information to determine the complete Latin square. It has been conjectured that the smallest possible critical set in a Latin square is of size b n
Disjoint critical sets in Latin squares Peter Adams, Richard Bean and Abdollah Khodkar Centre for Discrete Mathematics and Computing Department of Mathematics The University of Queensland Queensland 4072 Australia
ABSTRACT: A critical set in a Latin square is a subset of the Latin square containing just enough information to determine the complete Latin square. It has been conjectured that the smallest possible critical set in a Latin square is 2 of size b n c. If this conjecture is true, it may be possible to partition a Latin 4 square L into two, three or four disjoint critical sets in L. We give a theorem to show that for a given order n, there exists a back-circulant Latin square of order n which may be partitioned into four disjoint critical sets, and we give examples of all possible di erent partitions of Latin squares of order at most 6. We also give an example of two mutually complementary critical sets, which partition a Latin square of order 8 into two disjoint critical sets.
1 Introduction A partial Latin square P of order n is an n n array containing symbols chosen from a set N of size n in such a way that each element of N occurs at most once in each row and at most once in each column of the array. For ease of exposition, a partial Latin square P will be represented by a set of ordered triples f(i; j; k) j element k 2 N occurs in cell (i; j ) of the arrayg. If all the cells of the array are lled then the partial Latin square is termed a Latin square. That is, a Latin square L of order n is an n n array with entries chosen from the set N in such a way that each element of N occurs precisely once in each row and precisely once in each column of the array. A critical set in a Latin square L (of order n) is a partial Latin square C in L, such that (1) L is the only Latin square of order n which has element k in cell (i; j ) for each (i; j; k) 2 C, and (2) no proper subset of C satis es (1). 1
A note on critical sets 暂无评价 4页 免费 Tuples of Disjoint NP-Se.....The cardinality of the largest critical set in any Latin square of order ...
Disjoint critical sets i... 暂无评价 14页 免费 Critical sets for Latin ...Indexing terms : Room square, critical set, in uence, power, strong box,...
Disjoint critical sets i... 暂无评价 14页 免费 Critical sets for Latin ... and its Applications INFLUENCE OF ENTRIES IN CRITICAL SETS OF ROOM SQUARES...
Let LS(n) be the largest size square that can be covered by disjoint copies of some set S of polynominos with a total of n squares, such that ...
the associated partial latin square can be decomposed into six disjoint l.....critical sets in latin squares (see Donovan and Howse 2]) and de ning ...
critical sets in back circulant latin squares, to identify subsquare free ...They are said to be disjoint if no cell in I contains the same entry ...
multipartite graphs, orthogonal arrays, Latin squares and Room squares. ...The number of critical sets in a Room square of order are still unknown,...
Do there exist any Latin squares, other than Cayley tables, whose ... CA 93106 USA Consider two disjoint nite sets A and B , each ...
set of vertex labels {0, 1, 3, 5} and the...disjoint union of complete graphs is dependent ...families of mutually orthogonal Latin squares [4]...
2 mutually orthogonal latin squares (MOLS) of order n. It is well known...H = fH ; : : : ; H`g is a set of pairwise disjoint subsets of X...
s theorem: a set of mutually orthogonal n × n latin squares has at ...m = v/k disjoint blocks, called parallel classes, then D is resolvable....
我要评论