Timeline for How dense is the set of asymmetric graphs?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 27, 2014 at 0:38 | vote | accept | Mohammad Al-Turkistany | ||
| Jan 8, 2014 at 22:58 | comment | added | Brendan McKay | @Andrew: It isn't trivial, but isn't hard to prove. Take a random graph ($p=1/2$) and consider the probability $P(\pi)$ that a particular permutation is an automorphism. For a transposition it is $2^{-n+2}$, for a 3-cycle it is $2^{-2n+4}$. For a permutation moving $\Theta(n)$ points, the probability is $2^{-\Theta(n^2)}$. In the sum of $P(\pi)$ over all non-identity permutations $\pi$, the terms from transpositions dominate. This is folklore but I don't recall where it is in print. | |
| Jan 8, 2014 at 22:08 | comment | added | Andrew D. King | Is there a simple justification for your first sentence? | |
| Apr 22, 2013 at 4:12 | history | answered | Brendan McKay | CC BY-SA 3.0 |