4
$\begingroup$

Let $S=\{1,2,\dots,m+n-1\}$.

An $m\times n$ matrix($\in S^{m\times n}$) is called silver matrix if

(a) There is no same numbers in the row or column. (like latin square)

(b) {$i$ th row}$\cup${$i$ th column}=S for all $1\leq i\leq min(m,n)$

Does silver matrix exist for all $m\neq n$ ?

If this conjecture is true, $d(K_m\times K_n, m+n-1) = mn-min(m,n)$ ($m\neq n$)

($d$ is defining number, $\times$ is cartesian product)

$\endgroup$
6
  • $\begingroup$ What is the smallest value of $\max(m,n)$ for which you don't know the answer? $\endgroup$
    – Yemon Choi
    Feb 12, 2012 at 8:03
  • $\begingroup$ I want to prove this conjecture for all $m\neq n$. $\endgroup$ Feb 12, 2012 at 8:12
  • $\begingroup$ If you want to prove it for all such m and n, then presumably you can prove it for some particular values of m and n. Which is the smallest pair for which you do not yet know the answer? $\endgroup$
    – Yemon Choi
    Feb 12, 2012 at 8:37
  • $\begingroup$ (7,6). It looks possible, but I don't know the answer. $\endgroup$ Feb 12, 2012 at 11:25
  • 1
    $\begingroup$ Looks like the problem appears here: ams.org/notices/199709/people.pdf Still no idea what is the defining number so more elucidation is necessary. $\endgroup$ May 9, 2012 at 9:10

1 Answer 1

6
$\begingroup$

Yes. Silver matrices exist for all $n=m$ when $n$ is even and for all $n\neq m$. Notice that the problem for square matrices is essentially problem 4 in the 1997 International Math Olympiad.

One basic construction one needs is a symmetric latin square. These exist for all orders and are essentially equivalent to edge colorings of complete graphs. A symmetric latin square of even order can be taken to have a constant diagonal while a symmetric latin square of odd order must have all elements appearing exactly once on the diagonal.

Returning to your problem: Paste together the lower triangular part of a $2a\times 2a$ symmetric latin square and the upper triangular part of a $2b\times 2b$ symmetric latin square whose alphabets have only one letter in common, the one on the diagonal. Do this by identifying the last $c$ diagonal elements of the first with the first $c$ diagonal elements of the second. Where $c$ is some number with $c\le 2\min(a,b)$. This gives you a $c\times(2a+2b-c)$ silver matrix (take the obvious $c$ rows and rearrange the columns). So you get a construction for all $m,n$ both even or both odd but unequal. The case with $m-n$ odd can be dealt with similarly by playing around with symmetric latin squares of odd order.

$\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.