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