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.