Most Latin Squares Have Many Subsquares

摘要

A k * n Latin rectangle is a k * n matrix of entries from {1, 2, ..., n} such that no symbol occurs twice in any row or column. An intercalate is a 2 * 2 Latin subrectangle. Let N(R) be the number of intercalates in R, a randomly chosen k*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) >= n~(3/2 - #epsilon#). We also provide data from a computer enumeration of Latin rectangles for small k, n.