Timeline for Counting distinct undirected, partially labelled graphs
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2015 at 20:14 | comment | added | Ira Gessel | There's a proof of Pólya's theorem by Gian-Carlo Rota and David Smith using Möbius inversion along the lines that gowers suggests, but the usual proof of Burnside's lemma is much easier. See Rota, Gian-Carlo; Smith, David A. Enumeration under group action. Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Sér. 4, 4 no. 4 (1977), p. 637-646 numdam.org/item?id=ASNSP_1977_4_4_4_637_0 | |
| Mar 4, 2010 at 12:19 | comment | added | Douglas Zare | The standard method is Burnside's Lemma, that the number of orbits equals the average number of fixed points for a uniformly chosen element of the group. That still leaves the problem of counting symmetric configurations. | |
| Mar 4, 2010 at 12:02 | comment | added | gowers | Sorry, I meant triples closed under the given rotation (some, but not all, of which give you triangles). If the vertices are 0,1,2,3,4,5, then some examples of such triples are 01,23,45 and 03,14,25, and also the equilateral triangles 02,24,40 and 13,35,51. In fact, there's one more triple, namely 14,25,30, and any graph with rotational symmetry of order 3 is a union of these triples, so there are 32 such graphs. | |
| Mar 4, 2010 at 11:58 | history | edited | gowers | CC BY-SA 2.5 |
deleted 16 characters in body
|
| Mar 4, 2010 at 11:54 | comment | added | Nick Johnson | That seems like a reasonable approach. I'm not quite sure I understand how to count all graphs with a given rotational symmetry, though, or your comment about equilateral triangles. | |
| Mar 4, 2010 at 11:49 | history | answered | gowers | CC BY-SA 2.5 |