Timeline for Non-enumerative proof that there are many derangements?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2022 at 19:07 | comment | added | Michael Hardy | BEGIN QUOTE by computing moments (or factorial moments) or using generating function methods, one can establish the stronger result that the number of fixed points in a random permutation is asymptotically distributed according to a Poisson process of intensity 1. END QUOTE I'm not sure of the details that the OP has in mind here, but the first $n$ moments of the distribution of the number of fixed points are identical to the first $n$ moments of the Poisson distribution. The easy way to show that is to show that it's true of factorial moments and from that deduce that it's true of moments. | |
| Feb 6, 2022 at 19:04 | comment | added | Michael Hardy | $\ldots\,$ with respect to an underlying measure such as Lebesgue measure in the plane, is the "intensity." | |
| Feb 6, 2022 at 19:03 | comment | added | Michael Hardy | The phrasing "a Poisson process of intensity $1$" causes some hesitation. "a Poisson distribution of expected value $1$" is what I would say. A Poisson process is a more elaborate thing than a Poisson distribution. A Poisson process assigns a Poisson random variable to every measurable subset of some measure space (often a line or a plane) in such a way that the measure of that subset is the expected value of the Poisson distribution and if two such measurable sets are disjoint then those Poisson-distributed random variables are independent. That measure, or its derivative$\,\ldots\qquad$ | |
| Oct 12, 2012 at 6:47 | answer | added | Austin Mohr | timeline score: 17 | |
| Jan 24, 2012 at 11:41 | comment | added | Roland Bacher | A variation on Suvrit's argument above shows that there are at least roughly $(n−1)^{n/2}$ permutations without fixed points: Choose a Hadamard matrix of size $n$ (supposed to be divisible by 4) which is of the form $A+Id$ with $A$ antisymmetric (such matrices exist for example if $n=p+1$ where $p$ is a prime of the form $4k+3$). The number of derangement is of course at least equal to the absolute value of the determinant $\pm (n−1)^{n/2}$ of the matrix $A$. | |
| Jan 20, 2012 at 17:14 | vote | accept | Terry Tao | ||
| Jan 20, 2012 at 12:26 | answer | added | Brendan McKay | timeline score: 64 | |
| Jan 20, 2012 at 9:18 | comment | added | Zsbán Ambrus | So would you like some cobinatorial way to collect permutations to groups of at most 10 permutations where each group has at least one derangement? I wonder if there's a proof like that. | |
| Jan 20, 2012 at 0:27 | answer | added | Chris Godsil | timeline score: 12 | |
| Jan 20, 2012 at 0:05 | comment | added | Gerhard Paseman | Perhaps this is just deferring the enumeration part of the proof, but what about considering the proportion of cycle structures which have no fixed points? Perhaps that is bounded away from zero, and can be used in an inductive proof that the proportion of derangements is also bounded away from zero. Gerhard "Ask Me About System Design" Paseman, 2012.01.19 | |
| Jan 19, 2012 at 19:30 | comment | added | Kevin P. Costello | It feels like there should be some sort of proof by showing that conditioning a random permutation on $\pi(i) \neq i$ for $1 \leq i \leq j-1$ makes it more likely that $\pi(j) \neq j$. This seems intuitive enough (assuming that $\pi(i) \neq i$ makes it more likely that some $i$ has $\pi(i)=j$), but I don't see an obvious proof that doesn't use the same counting techniques that would already get you the full formula. | |
| Jan 19, 2012 at 19:25 | answer | added | Robert Israel | timeline score: 12 | |
| Jan 19, 2012 at 18:47 | answer | added | Liviu Nicolaescu | timeline score: 5 | |
| Jan 19, 2012 at 18:37 | history | edited | Terry Tao | CC BY-SA 3.0 |
added 8 characters in body
|
| Jan 19, 2012 at 18:21 | comment | added | Suvrit | Do you think the following elementary argument helps: The difference between the num of odd and even derangements is $(-1)^{n-1}(n-1)$, and this can be shown by evaluating a nice determinant, as shown in math.hmc.edu/~benjamin/papers/derangement.pdf | |
| Jan 19, 2012 at 18:14 | history | edited | Peter McNamara | CC BY-SA 3.0 |
fixed link to lovasz local lemma
|
| Jan 19, 2012 at 18:07 | answer | added | Barry Cipra | timeline score: 21 | |
| Jan 19, 2012 at 17:38 | history | asked | Terry Tao | CC BY-SA 3.0 |