3
$\begingroup$

The Evans conjecture ( which was proved later by Smetaniuk) states that for any $n$, if at most $n-1$ entries of a partial $n\times n$ latin square are filled, it can be completed to the full latin square.

My question pertains to whether this is applicable to symmetric (or commutative) latin square? That is, given $n\times n$ latin square, with at most $n-1$ prefilled entries ( which are symmetric with respect to diagonal), can it be completed to a symmetric latin square? Note that this corresponds to pre- total coloring of a complete graph of order $n$ with at most $n-1$ previous filled colors. Any hints? Thanks beforehand.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

No, when it comes to symmetric latin squares it is no longer true that as many as $n-1$ cells can be prescribed unconditionally. This is explained in the Ph.D. thesis of Matthew Henderson.

The key point here is that in a symmetric latin square, precisely because of the symmetry, every symbol $\sigma$ occurs an even number of times in cells outside of the main diagonal. Therefore, as every symbol $\sigma$ occurs $n$ times in total it follows that the number of cells of the main diagonal containing symbol $\sigma$ is congruent to $n$ modulo 2. A partial latin square can be incompletable because there are more symbols which occur on the main diagonal a number of times (zero included) incongruent to $n$ modulo 2 than there are empty cells on the main diagonal.
If this obstruction does not occur the diagonal is called "admissible". For $n$ odd a diagonal is admissible if and only if no symbol occurs more than once on it.

The generalization of Evans theorem to symmetric latin squares by Andersen and Hilton is that the symmetric latin square is completable if the diagonal is admissible and at most $n-1$ cells in total are prescribed.

In response to the comment by Richard Stanley: it is not sufficient to only count cells on or above the main diagonal, as this counter example shows. The diagonal is admissible ($n=5$ is odd and no symbol appears more than once on the diagonal), and the number of prescribed cells on or above the main diagonal is $n-1=4$, and yet the latin square is not completable.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Is this the only obstruction to completing a partial symmetric latin square with $n-1$ symbols? This might be the correct analogue of Evans conjecture for symmetric latin squares. Even more strongly, is it possible that you can specify $n-1$ symbols on or above the main diagonal, as long as you satisfy: (1) when you reflect the symbols about the main diagonal, we have a partial latin square, and (2) Carlo's condition? $\endgroup$
    – Richard Stanley
    Commented Sep 8, 2020 at 17:56
  • $\begingroup$ The problem mentions "Evans conjecture", this answer mentions "Evans theorem". Please, @RichardStanley or anyone else, clarify for me the relation (if any) between the two. $\endgroup$
    – Gerry Myerson
    Commented Sep 9, 2020 at 3:12
  • $\begingroup$ @GerryMyerson --- the completability condition for nonsymmetric Latin squares was conjectured by Evans in 1960 and proven by Smetaniuk in 1981. $\endgroup$
    – Carlo Beenakker
    Commented Sep 9, 2020 at 6:01
  • $\begingroup$ OK, so, there isn't an Evans theorem? $\endgroup$
    – Gerry Myerson
    Commented Sep 9, 2020 at 11:02
  • $\begingroup$ I'm not sure what the common practice is here, if a conjecture is proven can we then change its name into a theorem? Fermat's last theorem was called a conjecture in older books, but I guess it would be strange to keep calling it a conjecture now. There could be a confusion with other theorems of Evans, but the only one I found was the Evans-Krylov theorem. $\endgroup$
    – Carlo Beenakker
    Commented Sep 9, 2020 at 11:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .