Timeline for Conjugate subgraphs and (maybe) a generalized Burnside's lemma?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2014 at 5:15 | comment | added | Benjamin Dickman | mathoverflow.net/questions/169016/a-generalized-burnsides-lemma | |
| Aug 22, 2012 at 10:30 | comment | added | Emil Jeřábek | @Hans: I’m not sure, I’d say that your questions are borderline for MO. For this particular question, the problem is not that much in the level, but in its lack of specificity: as explained in the FAQ, you should ask “well-defined questions ... that actually have a specific answer”, rather than open-ended requests like “where do they play a role”. I can’t comment on MSE as I’m not active there, so I’m not familiar with the situation. | |
| Aug 21, 2012 at 16:07 | comment | added | Hans-Peter Stricker | @Emil: I really appreciate your comments (and answers), but I am insecure where to post my questions: posting them at math.stackexchange reveals mostly (almost) nothing - few views, very few comments and answers. But posting them at MO seems overkill: you experts seem annoyed. Nevertheless you give valuable comments, what I do appreciate a lot! So, what do you recommend? | |
| Aug 21, 2012 at 15:35 | comment | added | Emil Jeřábek | I’m not quite sure what kind of generalization of Burnside’s lemma you are after, but if you just want to count the number of subgraphs (with or without specified order) up to conjugation, you can apply Burnside’s lemma directly to the action of $\mathrm{Aut}(H)$ on subgraphs. | |
| Aug 21, 2012 at 15:30 | comment | added | Hans-Peter Stricker | @F: You guessed correctly: this was not my intention, I've been misled. | |
| Aug 21, 2012 at 14:27 | comment | added | Hans-Peter Stricker | Thanks for your valuable corrections. Starting with Emil's more appropriate and natural definition (which is equivalent to Aaron's) the questions remain: Is there another name for conjugate subgraphs? And where do they play a role? Or is Aaron's hint to Polya enumeration all there is to say? | |
| Aug 21, 2012 at 13:33 | comment | added | Emil Jeřábek | @Hans: My definition is not equivalent to yours, the condition is stronger (it requires all the vertex pairs to be conjugate via the same automorphism). What I am saying is that the concept you defined looks quite weird to me, whereas my proposal is close to the definition of conjugate subgroups (the only difference being that for groups, only inner automorphisms are taken into account), which I assumed was your original motivation. Also, note that what I wrote is equivalent to Aaron’s description (being in the same orbit of the natural action of Aut($H$) on subgraphs). | |
| Aug 21, 2012 at 13:16 | comment | added | Frieder Ladisch | As I understand it, your definition implies that any two subgraphs of the circular graph $C_n$ having the same number of vertices are "conjugate", since any two vertices of $C_n$ are conjugate. So conjugate subgraphs in your sense may not be isomorphic. Is this really your intention? | |
| Aug 21, 2012 at 12:49 | comment | added | Aaron Meyerowitz | I think Polya Enumeration can fit the bill for a generalization of Burnside's lemma. | |
| Aug 21, 2012 at 12:45 | comment | added | Hans-Peter Stricker | @Emil: If you are right and your definition is equivalent to mine, I would have to think about it more deeply (not to say "meditate"). At least, your definition seems more like a natural generalization. But if spelled out - how does it meet the intention? | |
| Aug 21, 2012 at 12:42 | comment | added | Aaron Meyerowitz | In the same orbit (of the natural action of AUT$(H)$ on subgraphs? But if conjugate is good enough for vertices then it should be good enough for subgraphs. | |
| Aug 21, 2012 at 12:37 | comment | added | Hans-Peter Stricker | That depends. $g(V(G)) = V(G')$ seems very condensed. At first sight, it's an equality between sets, isn't it? | |
| Aug 21, 2012 at 12:35 | comment | added | Emil Jeřábek | Wouldn’t it be more natural to say that $G$ and $G'$ are conjugate if there is an automorphism $g$ of $H$ such that $g(V(G))=V(G')$? | |
| Aug 21, 2012 at 12:30 | history | asked | Hans-Peter Stricker | CC BY-SA 3.0 |