Multiplication tables with all entries distinct

Here are some numerical results:

$$ \begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\\hline 1 & 1 & 2 & 3 & 4 & 5 \\ 2 & 2 & 6 & 8 & 10 & 14 \\ 3 & 3 & 8 & 15 & 21 & 24 \\ 4 & 4 & 10 & 21 & 28 & 36 \\ 5 & 5 & 14 & 24 & 36 & 54 \end{array} $$ The diagonal sequence eludes the OEIS.

Gerry's heuristic fails for $(5,3)$ and $(5,4)$, though in these cases there are optima where the smaller set is equal to his: $$ \begin{gather*} \{1,2,3\}, \{1,5,6,7,8\} \\ \{1,2,3,4\}, \{1,5,7,8,9\} \end{gather*} $$ Gerry's heuristic only gives $27$ and $44$ (instead of $24$ and $36$): $$ \begin{gather*} \{1,2,3\}, \{1,4,5,7,9\} \\ \{1,2,3,4\}, \{1,5,6,7,11\} \end{gather*} $$ Worse, for $\{5,5\}$, the best solution is obtained on a pair not including $\{1,2,3,4,5\}$: $$ \{1,2,3,4,6\},\{1,5,7,8,9\} $$ The best solution containing $\{1,2,3,4,5\}$ has value $55$ (compared to $54$): $$ \{1,2,3,4,5\}, \{1,7,8,9,11\} $$ This is always the case when $x \nmid M(x,y)$.

Let $M^*(x)$ denote $M(x,x)$ under the constraint that one of the sets is $\{1,\ldots,x\}$. For $x \leq 7$, $M^*(x)$ agrees with A033286 and A026102, but the next entry in these sequences is 152, while $M^*(8) = 160$.

I will use this post to catalog results and miscellaneous thoughts about the problem.

The optimal solution for the $(6,6)$ case is very simple; it has $A=\{1,\ldots ,6\}, B=\{a, 7,\ldots,11\}$ (where $a$ is some element of $A$, say 1), and $M=66$. Clearly no solution can reduce the largest element of $A$. Any solution that reduces the largest element of $B$ will create a second overlap with $A$ that must be addressed by increasing the largest element of $A$. But 66 is too small to be improved in this way: $7×9$ is out of reach and $8×8$ is forbidden. Nothing else can work since each set must contain an element of 6 or more.

The solution seems to be simple in this case because there is a good home for the problem child 6, which is best housed with 2 and 3. [Add reason later.] In the 5×5 case the partial solution $A=\{1,\ldots,5\}, B=\{a, 6,\ldots\}$ is dominated by $A=\{1,2,3,4,6\}, B=\{a, 5, \ldots\}$ for the same reason.

A choice of $A$ induces a graph on ${\Bbb N}\setminus A$ where there is an edge between $n$ and $n'$ whenever there exist $a, a'\in A$ with $a/a' = n/n'$. Legal choices of $B$ then correspond to independent sets in this graph, and it is usually easy to pick out the optimal $B$ for a given $A$.