Well-balanced covering of transpositions in $n$ elements - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T07:14:22Z http://mathoverflow.net/feeds/question/74592 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74592/well-balanced-covering-of-transpositions-in-n-elements Well-balanced covering of transpositions in $n$ elements Denis Serre 2011-09-05T15:58:04Z 2011-09-06T03:53:46Z <p>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}$.</p> <p>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\}.$$</p> <blockquote> <p>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)$?</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/74592/well-balanced-covering-of-transpositions-in-n-elements/74612#74612 Answer by Noam D. Elkies for Well-balanced covering of transpositions in $n$ elements Noam D. Elkies 2011-09-05T20:15:09Z 2011-09-05T20:21:58Z <p>$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.</p> <p>Suppose $r(f) &lt; k$, and suppose $f(l)$ overlaps some $f(m)$ with $0 &lt; |l-m| &lt; k$. We want to find some $l'\in{\bf Z}/N{\bf Z}$ such that:</p> <p>$f(l')$ does not overlap $f(m)$ for any $m \neq l$ with $|l-m| &lt; k$, and</p> <p>$f(l)$ does not overlap $f(m')$ for any $m' \neq l'$ with $|l'-m'| &lt; k$.</p> <p>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 &lt; 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.</p> http://mathoverflow.net/questions/74592/well-balanced-covering-of-transpositions-in-n-elements/74631#74631 Answer by Brendan McKay for Well-balanced covering of transpositions in $n$ elements Brendan McKay 2011-09-06T03:00:15Z 2011-09-06T03:53:46Z <p>Close to $n/2$ is possible. I'll do odd $n$ and leave even $n$ for someone else's pleasure.</p> <p>Let $m=(n-1)/2$. For $i=0,\ldots,n-1$ and $j=1,\ldots,m$, let $M(i,j)$ be the pair <code>$\{i-j,i+j\}$</code> (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).$$</p> <p>Graph theorists will note that this is a standard 1-factorization of <code>$K_n$</code> listed one factor at a time.</p> <p><code>$M(i,j_1)$</code> and <code>$M(i,j_2)$</code> are disjoint for <code>$j_1\ne j_2$</code>, so the only chance of two overlapping pairs being closer than $m$ positions is two pairs of the form <code>$M(i,j_1)$</code> and <code>$M(i+1,j_2)$</code>. 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$.</p> <p>There are $n-1$ pairs <code>$\{0,j\}$</code>, 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.</p> <p>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$.</p>