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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.