2
$\begingroup$

I'm brainstorming an idea for storing a compressed list of main class representatives of Latin squares of order $9$. One way to compress the list would be to store one Latin square $L_1$, and for $i \geq 2$, store the Latin trade between $L_i$ and $L_{i-1}$. We can reduce the size of the Latin trade by replacing $L_i$ by another main class representative that agrees with $L_{i-1}$ in more positions. However, main classes of Latin squares of order $9$ usually contain $6 \times 9!^3>10^{17}$ Latin squares, which is too many to look at exhaustively.

Question: Given two Latin squares, $L$ and $M$, of order $9$, which Latin square $M'$ in the same main class as $M$ agrees with $L$ in the most cells? How can we generate it?

I'm seeking an algorithmic answer (something implementable), and practical approximations would suffice.

Improve this question
$\endgroup$
2
  • $\begingroup$ How do the ideas you have already work for lower orders (8, etc.)? Does the fact that 9=3*3 help, perhaps by collecting classes whose difference is represented by permuting a sub-Latin square of order 3? Not knowing how to tell when two squares are in the same class, I am hesitant to offer explicit suggestions. Gerhard "Combinatorialists Are Rather Classy Mathematicians" Paseman, 2016.09.15. $\endgroup$
    – Gerhard Paseman
    Sep 15, 2016 at 20:18
  • $\begingroup$ In the broad (i.e., replacing 9 here with an arbitrary value) I'd be very surprised if this problem (in particular the binary question 'is there a LS in the same class as $M$ which agrees with $L$ on all but $k$ squares') isn't NP-hard; I suspect that even answering whether two squares are in the same equivalence class is hard in some suitable sense (and indeed, sav.sk/journals/uploads/0317154604gr-sy.pdf seems to suggest this, and points to a reference ("On the $n\log n$ isomorphism technique") for more info, though there have been recent advances in graph and group isomorphism..) $\endgroup$
    – Steven Stadnicki
    Feb 12, 2017 at 17:46

1 Answer 1

Reset to default
1
$\begingroup$

I don't know the answer to the question you ask, but the way to achieve your objective is probably to use the main class reps in the order they come out of an orderly generator. Usually only the last few rows will change between squares, and if you omit the redundant last row altogether there might only be a few entries different on average.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.