4
$\begingroup$

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.

Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. Define the interleaving $I(\pi)$ to be the largest $d$ such that there are $i\in [n]$, $1\leq k\leq n$ such that $\delta(S)=d$ for $S = \{i, \pi(i),\dotsc, \pi^{k-1}(i)\}$.

For fixed $n$, how many $n$-cycles $\pi$ are there with given $I(\pi)$? Asymptotically, how common are $n$-cycles with $I(\pi)$ less than a given $r$, say?

Improve this question
$\endgroup$
11
  • $\begingroup$ Not that it isn't obvious, but in the definition of $\delta(S)$ a parameter other than $n$ in the second half might be convenient (since it's bound in the first half). Slightly more seriously should we interpret $n+1$ to equal 1? That is, is $\delta(\{1,n\})$ equal to 1 or to 2? $\endgroup$
    – Michael Albert
    Commented Sep 7, 2019 at 22:57
  • $\begingroup$ Ooops, changed. $\endgroup$
    – H A Helfgott
    Commented Sep 7, 2019 at 22:58
  • $\begingroup$ On whether $n+1$ equals $1$: whatever makes you happier. $\endgroup$
    – H A Helfgott
    Commented Sep 7, 2019 at 23:15
  • $\begingroup$ It looks that usually interleaving is about $n/4$: if we take a random subset $T$ with $\alpha n$ elements, it has about $\alpha(1-\alpha)n$ elements $x$ for which $x+1\notin T$, that is maximal for $\alpha=1/2$. And concentration inequalities show that greater interleaving is very unlikely (even after we multiply by the choice of $i$ and $k$ in your terms), and smaller interleaving is very unlikely even for $i=1,k=[n/2]$. $\endgroup$
    – Fedor Petrov
    Commented Sep 8, 2019 at 9:09
  • $\begingroup$ Sure, but how unlikely is unlikely? How many $\pi$ are there with $I(\pi)$ bounded? Is it about $O(C^n)$ or thereabouts, or is it more like $n!/2^n$? $\endgroup$
    – H A Helfgott
    Commented Sep 8, 2019 at 11:26

0

Reset to default

You must log in to answer this question.