Most Latin squares have many subsquares

被引:36
作者
McKay, BD [1 ]
Wanless, IM [1 ]
机构
[1] Australian Natl Univ, Dept Comp Sci, Canberra, ACT 0200, Australia
关键词
D O I
10.1006/jcta.1998.2947
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A k x n Latin rectangle is a k x n matrix of entries from {1, 2...., n} such that no symbol occurs twice in any row or column. An intercalate is a 2x2 Latin subrectangle. Let N(R) be the number of intercalates in R, a randomly chosen k x n Latin rectangle. We obtain a number of results about the distribution of N(R) including its asymptotic expectation and a bound on the probability that N(R)= 0. For epsilon>0 we prove most Latin squares of order n have N(R)greater than or equal to n(3/2-epsilon). We also provide data from a computer enumeration of Latin rectangles for small k,n. (C) 1999 Academic Press.
引用
收藏
页码:323 / 347
页数:25
相关论文
共 14 条
[1]  
[Anonymous], 1991, J COMBIN MATH COMBIN
[2]  
DENNISTON RHF, 1978, UTILITAS MATHEMATICA, V13, P299
[3]   ASYMPTOTIC ENUMERATION OF LATIN RECTANGLES [J].
GODSIL, CD ;
MCKAY, BD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :19-44
[4]  
HEINRICH K, 1981, LECT NOTES MATH, V884, P221
[5]  
Jacobson MT, 1996, J COMB DES, V4, P405, DOI 10.1002/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO
[6]  
2-J
[7]   CERTAIN CONSTRUCTIONS FOR LATIN SQUARES WITH NO LATIN SUBSQUARES OF ORDER 2 [J].
KOTZIG, A ;
TURGEON, J .
DISCRETE MATHEMATICS, 1976, 16 (03) :263-270
[8]  
Kotzig A., 1975, Utilitas Math, V7, P287
[9]  
MCKAY BD, 1995, ELECTRON J COMB, V2, pN3
[10]  
McLeish M., 1975, Utilitas Math, V8, P41