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 sub-rectangle. 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 ε>0 we prove most Latin squares of order n have N(R) ≥ n3/2-ε. We also provide data from a computer enumeration of Latin rectangles for small k,n.

Click here to download the whole paper.