Skip to main content
10 events
when toggle format what by license comment
Jan 23, 2012 at 21:50 comment added Brendan McKay Yes, the wording was poor. I changed it. The two operations need to be inverse. A more formal treatment would be to define a (multi-)relation between the sets {permutations with 0 fixed points} and {permutations with 1 fixed points} then count the pairs of the relation in two ways.
Jan 23, 2012 at 21:44 history edited Brendan McKay CC BY-SA 3.0
tweaks
Jan 23, 2012 at 19:24 comment added Timothy Chow In case anyone trips over the same mental block I had: I found Step 2 easier to follow when I replaced the last few words by, "...that create it from a permutation with no fixed points."
Jan 21, 2012 at 0:10 history edited Brendan McKay CC BY-SA 3.0
add irrelevant comment
Jan 21, 2012 at 0:09 comment added Brendan McKay @Johan, Yes, to get a lower bound switching just two elements will suffice. Switching three gives easier counting if bounds in both directions are required.
Jan 20, 2012 at 17:14 vote accept Terry Tao
Jan 20, 2012 at 17:14 comment added Terry Tao Thanks, this is exactly the sort of thing I was looking for - among all the methods proposed, this seems to be the most robust (in particular, it seems to easily give the second claim in the question, namely that l random permutations generate a 2l-regular graph with probability bounded away from zero, by switching away the problematic edges).
Jan 20, 2012 at 16:33 comment added Barry Cipra @Johan, I think what you're saying is along the lines of what I added to my answer after seeing Brendan's solution.
Jan 20, 2012 at 16:13 comment added Johan Wästlund I guess you rotate three elements (instead of just 2) so that the claim in (2) will hold for all permutations, not just almost all? But this is not necessary in order to reach the conclusion in (3). I was thinking about swapping the first element with the unique fixed point, and inversely swapping the first element to its proper place. This provides an almost-bijection between derangements and permutations with exactly one fixed point.
Jan 20, 2012 at 12:26 history answered Brendan McKay CC BY-SA 3.0