Let $A$ be an order-$n$ Latin square. A $k$-plex of $A$ is a set of entries , $k$ from each row and column and $k$ from each symbol.

My question is: Is there a Latin square with a large number of $k$-plexes?

More specifically, I am interested in this question for $k = \lambda n$ for some constant $0<\lambda\leq 1$ and for $n$ tending to infinity, and I want to show that the number of plexes is at least $$ e^{-o(n^2)} \cdot \binom{n^2}{\lambda n^2} $$

Initially, I thought that every Latin square should have many plexes. My intuition was that if each entry is chosen uniformly at random with probability $\lambda$, then the following events should be positively correlated.

$A$ - There are $\lambda n$ entries in each row.

$B$ - There are $\lambda n$ entries in each column.

$C$ - There are $\lambda n$ entries with each symbol.

Indeed, a paper by Ordentlich and Roth shows that $A$ and $B$ are positively correlated, and the same reasoning can show the same for $A,C$ and $B,C$. However, the paper "A Generalisation of Transversals for Latin Squares" by Wanless contains a construction of Latin squares with no $k$-plex when $k$ is odd, so the above argument can't hold for every Latin square.

So my question is: For a given $\lambda$, are there Latin squares (for every large enough $n$) with at least $e^{-o(n^2)} \cdot \binom{n^2}{\lambda n^2}$ $\lambda n$-plexes?

  • $\begingroup$ This doesn't help you solve the problem, but I'm pretty sure the paper by "Wanless and Church" you mentioned is actually a single-authored paper. The supposed second author "Christ Church" isn't a person. It's a college in the University of Oxford the author was affiliated with. $\endgroup$ – Yuichiro Fujiwara Jan 21 '15 at 16:28
  • $\begingroup$ Oops, thank you! $\endgroup$ – Zur Luria Jan 21 '15 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.