Well-balanced covering of transpositions in $n$ elements - MathOverflow

Well-balanced covering of transpositions in $n$ elements

2011-09-05T15:58:04Z

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.

Answer by Noam D. Elkies for Well-balanced covering of transpositions in $n$ elements

2011-09-05T20:15:09Z

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

Answer by Brendan McKay for Well-balanced covering of transpositions in $n$ elements

2011-09-06T03:00:15Z

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