Timeline for Number of valid topologies on a finite set of n elements
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2009 at 18:38 | comment | added | Qiaochu Yuan | If the permanent were constant on conjugacy classes then it would be equal to the determinant. (Note that the two coincide for diagonal matrices.) | |
| Dec 15, 2009 at 18:35 | comment | added | Harrison Brown | Okay, for planar graphs sure, but not in general. Absolutely, determinants are considerably more natural. Actually, is the permanent even constant on conjugacy classes? Probably, but not for as obvious reasons as the determinant. | |
| Dec 15, 2009 at 18:18 | comment | added | Qiaochu Yuan | Right, but for planar graphs one can get away with the Pfaffian. The reason to prefer determinants for exact enumeration is that there are a lot of ways to evaluate determinants - one of the cleanest, for example, is if the matrix has enough structure that one can write down its eigenvalues explicitly. | |
| Dec 15, 2009 at 17:38 | comment | added | Harrison Brown | Sets with a G action can be thought of as a particular kind of groupoid. It turns out that occasionally, for Burnside/Polya type results, you just need this groupoid structure plus some ad-hoc, group-action-like properties. In particular it can be fruitful to think about setoids, i.e. sets with equivalence relation. And there is a (straightforward!) characterization of topologies on [n] as the quotient of an easy-to-enumerate set by a certain equivalence relation. Which set and which relation is left as an exercise; unfortunately the one I'm thinking of doesn't have nice enough properties. | |
| Dec 15, 2009 at 17:25 | comment | added | Harrison Brown | Two comments. The short one first, since the long one is gonna be looong. Perfect matchings are usually enumerated by computing a permanent, not a determinant. Permanents are, like Qiaochu said, crazy useful; actually, computing the permanent of a matrix is #P-complete, where #P is a class of counting problems roughly analogous to NP (but considerably bigger and badder -- see e.g. Toda's theorem). | |
| Dec 15, 2009 at 15:16 | history | answered | Qiaochu Yuan | CC BY-SA 2.5 |