2
$\begingroup$

Hey Math Overflow!

Say we have a (simple) graph $\Gamma$, and $G=Aut(\Gamma)$ .

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\ ?$

I suspect that the answer is 'no'.

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.

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$.

Am I correct so far?

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(\Gamma)$.

I know that $Z(G,1+x) = 1+x+2x^2+4x^3+5x^4+5x^5+4x^6+...+x^9$

(the graph in question is $L_2(3)$)

Thanks in advance!

Shay

Edit1: Proper notations.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ One obvious comment: G is in general neither vertex- nor edge-transitive. Vertices are induced subgraphs on 1 vertex, edges are induced subgraphs on 2 vertices. If a graph has your property, then its automorphism group must be vertex- and edge-transitive. Both are very restrictive properties which can be falsified by one look at the graph in most cases. $\endgroup$
    – Johannes Hahn
    Commented Dec 4, 2011 at 12:15

3 Answers 3

Reset to default
4
$\begingroup$

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 < p < 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.

Sadly, with high probability he automorphism group of random graphs is empty... :-)

See the book "Bollobas - Random Graphs" for all of those things.

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 edge-transitivity.

http://en.wikipedia.org/wiki/Edge-transitive_graph

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)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Oh, of course! Edge Transitivity! Is this a sufficient condition though? That is: if $Gamma$ is Edge-Transitive then every 2 induced subgraph are isomorphis iff they are in the same orbit? $\endgroup$
    – Shaywei
    Commented Jul 16, 2011 at 12:25
  • $\begingroup$ @ Shaywei: Edge transitivity is not enough for that. I am actually sure that no kind of transitivity that only talks about subgraphs of bounded size will be enough for what you want. You need something like the condition that holds in the infinite random graph, every isomorphism between finite subgraphs extends to the whole graph. Now, technically what you are asking for is a bit less: You only need that some isomorphism of isomorphic subgraphs extends to the large graph. $\endgroup$
    – Stefan Geschke
    Commented Jul 16, 2011 at 12:33
  • $\begingroup$ OK, I think I understand things better now. Thanks for all the help guys. $\endgroup$
    – Shaywei
    Commented Jul 16, 2011 at 13:23
2
$\begingroup$

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:

http://books.google.com/books?id=nld40slgtdkC&pg=PA272&lpg=PA272&dq=Sheehan+and+Gardiner+homogeneous+graphs&source=bl&ots=eqDmjVVUk3&sig=kyihHJBGy1sfPhmpa6vaXoObbmQ&hl=en&ei=c9ejTprxGubY4QTyhfHaBA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CB0Q6AEwAA#v=onepage&q=Sheehan%20and%20Gardiner%20homogeneous%20graphs&f=false

Improve this answer
$\endgroup$
0
$\begingroup$

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.

There are various interesting results concerning related questions:

Rado's countably infinite random graph has the property that every isomorphism between two finite induced subgraphs extends to the whole graphs.

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ $L_2(3)$ is the lattice graph or order 3, also known as Hamming graph H(2,3). Here is an explanation and a picture: win.tue.nl/~aeb/graphs/Hamming.html Thank you for your reply and the example provided. Still, I'm not much close to understand my problem. Rado's example and Hrushovski's result are too general for my purpuse. More clarifications will be welcome. Shay $\endgroup$
    – Shaywei
    Commented Jul 16, 2011 at 11:54
  • $\begingroup$ Thanks for this clarification. What I can tell you is that the graph H(2,3) is both vertex and edge transitive. This can be seen using automorphisms that are induced by 1) reversal of the words that form the vertices and 2) permutations of the 3 characters in the alphabet. Do you know an automorphism that is not of this form? Since you know the cycle structure, you already know a lot about this graph, certainly more than I do. $\endgroup$
    – Stefan Geschke
    Commented Jul 16, 2011 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .