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.



Well-balanced covering of transpositions in $n$ elements
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$.


