Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let me denote $X_n$ the set of transpositions in $n$ elements. Equivalently, $X_n$ is the set of doubletons in $[1,n]\times[1,n]$. The cardinality of $X_n$ is $N=\frac{n(n-1)}{2}$.

If $f:{\mathbb Z}/N{\mathbb Z}\rightarrow X_n$ is a bijection, let us denote $$r(f):=\min\{|\ell-m|;\ell\ne m\quad\hbox{and}\quad f(\ell)\cap f(m)\ne\emptyset\}.$$ Finally, let us define $$R_n:=\max\{r(f);\hbox{bijections}\quad f:{\mathbb Z}/N{\mathbb Z}\rightarrow X_n\}.$$

What is the asymptotics of $R_n$ as $n\rightarrow+\infty$. Is it $R_n\sim cn$ for some $c\in(0,\frac12)$? Or do we have $R_n=o(n)$?

My motivation comes from a numerical algorithm due to Jacobi for the calculation of the spectrum of Hermitian matrices. Each step operates on a pair of rows/columns, with the effect of settong the entry $a_{ij}$ to zero. Once one has act on a row, it seems better to avoid coming back to it too soon. On an other hand, one needs to visit every pairs $(i,j)$ every $N$ steps.

share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

Close to $n/2$ is possible. I'll do odd $n$ and leave even $n$ for someone else's pleasure.

Let $m=(n-1)/2$. For $i=0,\ldots,n-1$ and $j=1,\ldots,m$, let $M(i,j)$ be the pair $\{i-j,i+j\}$ (all values taken mod $n$, of course). The solution is $$ M(0,1).\ldots,M(0,m),M(1,1),\ldots,M(1,m),\ldots,M(n-1,1),\ldots,M(n-1,m).$$

Graph theorists will note that this is a standard 1-factorization of $K_n$ listed one factor at a time.

$M(i,j_1)$ and $M(i,j_2)$ are disjoint for $j_1\ne j_2$, so the only chance of two overlapping pairs being closer than $m$ positions is two pairs of the form $M(i,j_1)$ and $M(i+1,j_2)$. A little thought shows that $M(i,j)$ overlaps $M(i+1,j-1)$ and $M(i+1,j+1)$ and no other pairs $M(i+1,j')$. Thus the minimum separation is $m-1=(n-3)/2$.

There are $n-1$ pairs $\{0,j\}$, so two of them must be at most distance $\lfloor N/(n-1)\rfloor = (n-1)/2$, still assuming $n$ is odd. This shows that the solution above is at most 1 worse than the optimum.

EDIT: For even $n$, $(n-2)/2$ is achievable and is optimal. The remaining loose end is whether $(n-1)/2$ is possible for odd $n$.

share|improve this answer
    
That's very neat. I tried for something like that but couldn't do better than $n/4$. –  Noam D. Elkies Sep 6 '11 at 4:25
    
Thanks. In the case of $n$ odd and separation $m=(n−1)/2$, any $m$ pairs in a row must be a matching, and any $2m$ in a row must be a hamiltonian path. I didn't find such a solution for $n=5$ but I didn't yet try systematically. –  Brendan McKay Sep 6 '11 at 5:22
    
Unless my program has a bug (for the first time ever ;), there are no solutions for $n$ odd and separation $m=(n−1)/2$ with $5\le n\le 23$. So I conjecture that $(n-3)/2$ is optimal. –  Brendan McKay Sep 6 '11 at 9:40
    
And of course, $n$ odd implies that the map $(i,j)\mapsto(i-j,i+j)$ is a bijection. –  Denis Serre Sep 6 '11 at 12:50
add comment

$R_n \geq n/16$ can be obtained by starting from an arbitrary $f$ and then switching pairs of transpositions to get rid of any overlapping pairs whose images are too close to each other.

Suppose $r(f) < k$, and suppose $f(l)$ overlaps some $f(m)$ with $0 < |l-m| < k$. We want to find some $l'\in{\bf Z}/N{\bf Z}$ such that:

$f(l')$ does not overlap $f(m)$ for any $m \neq l$ with $|l-m| < k$, and

$f(l)$ does not overlap $f(m')$ for any $m' \neq l'$ with $|l'-m'| < k$.

Now any transposition overlaps with $2n-4$ others. Thus each of our two conditions excludes at most $(2n-4) (2k-2)$ choices of $l'$. We must also exclude the $2n-4$ choices of $l'$ such that $f(l')$ itself overlaps with $f(l)$. As long as $N-1 > (2n-4)(4k-3)$, we can find such $l'$. Since $N = (n^2-n)/2$, this condition is satisfied as long as $k < n/16 - O(1)$; indeed since $N-1 = (n-2)(n+1)/2$ our condition simplifies to $k \leq (n+13)/16$. So if $k \leq (n+13)/16$ we can switch two transpositions so as to increase by at least $1$ the number of transpositions without an offending overlap. Doing this at most $N$ times yields a bijection $f: {\bf Z}/N{\bf Z} \rightarrow X_n$ with $r(f) \geq k$, as claimed.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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