1
$\begingroup$

Suppose $ S_{n,N} $ be the set of $n$ elements with $N$ many cycles where $N$ is proportional to $n$. $U_{n,N}$ is an element picked randomly from this. It is known that the length of any cycle cannot be too large. What if we restrict the cycle lengths to be odd and then pick uniformly from this? Should it be also be that there are no cycles with huge length w.h.p?

I can prove this is the case if cycle lengths are all even. Is there any known reference for this?

Thanks

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Please edit your question to clarify it. Is $S$ a "set of $n$ elements" as you say, or a set of permutations of $n$ elements? And should "with $N$ many cycles" be "with $N$ cycles"? $\endgroup$
    – Brendan McKay
    May 14, 2012 at 3:05
  • $\begingroup$ @gmath: It would also be nice to have the references of the two results you mentioned. $\endgroup$
    – John Jiang
    May 14, 2012 at 5:25
  • $\begingroup$ Do you mean that fixing the constant of proportionality between $n$ and $N$ and letting $n$ grow, there is a size $C$ so that with probability approaching $1$ the longest cycle is shorter than $C$ (or $C \log{n}$ or something like that?) Be more specific please. $\endgroup$
    – Aaron Meyerowitz
    May 14, 2012 at 6:10
  • $\begingroup$ Although I don't see all of the details, the result for odd cycles should follow from the result for even cycles by combining pairs of cycles of odd length into cycles of even length. $\endgroup$
    – Douglas Zare
    May 14, 2012 at 14:49
  • $\begingroup$ @Brendan: Yes you are right. $S_{n,N}$ is the set of permutations of a set of $n$ elements with $N$ cycles. Sorry for being sloppy. $\endgroup$
    – gmath
    May 15, 2012 at 0:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.