5,216 reputation
829
bio website cs.ox.ac.uk/people/…
location Oxford, United Kingdom
age 51
visits member for 4 years, 5 months
seen 28 mins ago

24m
comment Complexity :: Integer Programming :: Non-Poly Example
the notions of NP-completeness and polynomial-time solvability are about classes of problems, and not individual examples.
10h
comment Mysterious identity between numbers of odd/even meander systems
I bet this is a relatively easy exercise with generating functions; a one Richard Stanley can do in his head :-)
10h
comment Mysterious identity between numbers of odd/even meander systems
So, do you have explicit formulae for $OMS$ and $EMS$, or not?
10h
comment Mysterious identity between numbers of odd/even meander systems
then what kind of "explicit expressions" are you talking about?
10h
comment Mysterious identity between numbers of odd/even meander systems
Then why do you ask "whether this is true"? So the numbers are the same, as you just said. Do you rather ask for an explicit bijection?
10h
comment Mysterious identity between numbers of odd/even meander systems
Did you try putting your numbers into oeis.org and see what it tells you?
1d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
@QiaochuYuan - right, I missed this point.
1d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
@QiaochuYuan - the behaviour of a permutation matrix is not determined by the order alone; it is determined by the cyclic structure of the permutation. E.g. the multiplicity of eigenvalue 1 is the number of cycles.
2d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
a similar argument works for elements of order 3; as an eigenvalue $\lambda$ and its conjugate must occur with the same multiplicity, we see that the number of eigenvalues equal to 1 must be equal to twice the number of eigenvalues $\zeta$, for $\zeta$ a fixed primitive cubic root of unity.
2d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
for the elements of order 2, it's trivial that the number of eigenvalues equal to 1 equals the number of eigenvalues equal to -1, as the trace of each non-identity element equals to 0.
2d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
@Anirbit: ARupinski claims something for the regular representation (of any finite group) only; Stembridge gives formulae for the irreducible representations of $S_n$, which is a completely different story.
2d
comment Is anything known about the eigenspectrum of the regular representation of the permutation group?
there is no contradiction; well, I don't see immediately how to (dis)prove ARupinski's statement, but it was probably already known to Frobenuis...
Apr
24
comment A digraph related to permutations
takes 0.5 sec on my laptop (n is the number after $6!^{720}$)
Apr
24
comment A digraph related to permutations
sage: factor(n) 2^307 * 3^120 * 5^19 * 7^128 * 11 * 13^3 * 19^44 * 31 * 43^44 * 47 * 61 * 113^6 * 127 * 131 * 139^2 * 241 * 1031 * 1481^2 * 1531 * 1621^2 * 1699^2 * 2801^3 * 5147 * 10607 * 47917^2 * 90803^2 * 548521 * 685367 * 2460593 * 47389957 * 2920679263^2 * 8428156447^2 * 216271121699 * 285106814092712039^2
Apr
23
comment Ordered lattice point enumeration
@SteveHuntsman - LattE will only count the points
Apr
23
comment A digraph related to permutations
actually, I wonder if BEST really applies, as $P_n$ has degree $n$, whereas for BEST one would want degree $n+1$, at least naively.
Apr
22
comment Synthetic projective definition of cubic curves
@MikeShulman - this is some particular kind of divisor, IIRC...
Apr
22
comment A digraph related to permutations
@DavidFeldman, sure, you're welcome!
Apr
22
comment A digraph related to permutations
then this asks for en.wikipedia.org/wiki/BEST_theorem
Apr
22
comment A digraph related to permutations
if you consider en.wikipedia.org/wiki/De_Bruijn_graph, more precisely the one on $n^n$ vertices, then your graph is a subgraph where each vertex corresponds to a permutation of $n$ symbols, right?