5
$\begingroup$

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?

$\endgroup$
2
  • $\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$ Commented Jan 21, 2015 at 16:28
  • $\begingroup$ Oops, thank you! $\endgroup$
    – Zur Luria
    Commented Jan 21, 2015 at 16:50

0

You must log in to answer this question.

Browse other questions tagged .