Induced Subgraphs and Orbits of the automorphism group action - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T04:49:29Z http://mathoverflow.net/feeds/question/70492 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70492/induced-subgraphs-and-orbits-of-the-automorphism-group-action Induced Subgraphs and Orbits of the automorphism group action Shaywei 2011-07-16T11:21:08Z 2012-01-29T12:22:12Z <p>Hey Math Overflow!</p> <p>Say we have a (simple) graph $\Gamma$, and G=Aut($\Gamma$) .</p> <p>Is it true (in general) that 2 induced subgraphs of $\Gamma$, say $\Gamma_1$ and $\Gamma_2$, are isomorphic iff they are in the same orbit of the action of G?</p> <p>I suspect that the answer is 'no'.</p> <p>First, I think one side is true and is trivial: If they are in the same orbit then there is an automorphism that, restricted to the vertices of $\Gamma_1$ and $\Gamma_2$ is an isomorphism.</p> <p>However, I don't know, that given an isomorphism between $\Gamma_1$ and $\Gamma_2$ if we can extend it to an automorphism on $\Gamma$.</p> <p>Am I correct so far?</p> <p>Also, given a graph, how do I go about to show that for this specific graph this argument is true (while not being true in general)? I suspect that it has some connection to the cycle index of the action of G on V.</p> <p>I know that $Z(G,1+x) = 1+x+2x^2+4x^3+5x^4+5x^5+4x^6+...+x^9$</p> <p>(the graph in question is $L_2(3)$)</p> <p>Thanks in advance!</p> <p>Shay</p> <p>Edit1: Proper notations.</p> http://mathoverflow.net/questions/70492/induced-subgraphs-and-orbits-of-the-automorphism-group-action/70494#70494 Answer by Stefan Geschke for Induced Subgraphs and Orbits of the automorphism group action Stefan Geschke 2011-07-16T11:39:12Z 2011-07-16T11:39:12Z <p>What is L_2(3)? But you are on the right track. Not every isomorphism between the two induced subgraphs has to extend to the whole structure. The simplest example is this: Take one edge together with an isolated vertex. Any two one element subgraphs are isomorphic, but there is no isomorphism of the full graph that moves the isolated vertex to one of the nonisolated vertices.</p> <p>There are various interesting results concerning related questions:</p> <p>Rado's countably infinite random graph has the property that every isomorphism between two finite induced subgraphs extends to the whole graphs.</p> <p>Hrushovski proved that every finite graph $F$ is the induced subgraph of a finite graph $G$ such that every isomorphism between induced subgraphs of $F$ extends to an automorphism of $G$. </p> http://mathoverflow.net/questions/70492/induced-subgraphs-and-orbits-of-the-automorphism-group-action/70499#70499 Answer by Nathann Cohen for Induced Subgraphs and Orbits of the automorphism group action Nathann Cohen 2011-07-16T12:14:33Z 2011-07-16T12:14:33Z <p>Random graphs, once again. When you consider a random graph $G_{n,p}$ (you have $n$ vertices and create each of the any $\binom n 2$ edges with probability $p$), it can be proved that for any $0 &lt; p &lt; 1$ and any graph $H$ the graph $G_{n,p}$ contains an induced copy of $H$ with probability $1$ when $n\rightarrow \infty$. The same proof easily tells you that there are at least two (well, just consider instead of $H$ the graph $H+H$ and apply the result again) induced copies of $H$ in your graph.</p> <p>Sadly, with high probability he automorphism group of random graphs is empty... :-)</p> <p>See the book "Bollobas - Random Graphs" for all of those things.</p> <p>Oh. And I actually forgot the most basic answer. If your conjecture is true, then surely it must work when $\Gamma_1$ and $\Gamma_2$ is an edge, i.e, one of the two graphs on two vertices. The property that there exists for any pair of edges $e,e'$ an automorphism of $G$ turning $e$ into $e'$ is called <em>edge-transitivity</em>.</p> <p><a href="http://en.wikipedia.org/wiki/Edge-transitive_graph" rel="nofollow">http://en.wikipedia.org/wiki/Edge-transitive_graph</a></p> <p>Not all graphs are edge transitive. The easiest possible example is to take in a graph two edges $uv$ and $u'v'$ such that {$d_G(u),d_G(v)$}$\neq${$d_G(u'),d_G(v')$}. Then surely there is no automorphism of $G$ turning the first edge into the second one (take any tripartite complete graph with sets of different sizes)</p> http://mathoverflow.net/questions/70492/induced-subgraphs-and-orbits-of-the-automorphism-group-action/78879#78879 Answer by Colin Reid for Induced Subgraphs and Orbits of the automorphism group action Colin Reid 2011-10-23T09:10:12Z 2011-10-23T09:10:12Z <p>Finite graphs which are homomogeneous, that is, every isomorphism between induced subgraphs extends to an automorphism, are extremely special and have been classified. Indeed, even the graphs which are homomogeneous on induced subgraphs of size $\le 3$ have been classified. See for instance: </p> <p><a href="http://books.google.com/books?id=nld40slgtdkC&amp;pg=PA272&amp;lpg=PA272&amp;dq=Sheehan+and+Gardiner+homogeneous+graphs&amp;source=bl&amp;ots=eqDmjVVUk3&amp;sig=kyihHJBGy1sfPhmpa6vaXoObbmQ&amp;hl=en&amp;ei=c9ejTprxGubY4QTyhfHaBA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CB0Q6AEwAA#v=onepage&amp;q=Sheehan%20and%20Gardiner%20homogeneous%20graphs&amp;f=false" rel="nofollow">http://books.google.com/books?id=nld40slgtdkC&amp;pg=PA272&amp;lpg=PA272&amp;dq=Sheehan+and+Gardiner+homogeneous+graphs&amp;source=bl&amp;ots=eqDmjVVUk3&amp;sig=kyihHJBGy1sfPhmpa6vaXoObbmQ&amp;hl=en&amp;ei=c9ejTprxGubY4QTyhfHaBA&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CB0Q6AEwAA#v=onepage&amp;q=Sheehan%20and%20Gardiner%20homogeneous%20graphs&amp;f=false</a></p>