Is there a graph family on $n$-vertices such that any graph $G$ in the family have small automorphism group (say $|Aut(G)|\leq n^c$ for some fixed $c>0$) which if $G$ and $H$ are isomorphic then the set of isomorphic permutations $Iso(G,H)$ from $G$ to $H$ is very large (say $|Iso(G,H)|\geq n^{c'n}$ for some fixed $c'>0$)? If so is there a constructive procedure?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ One of us is confused. Surely the number of permutations mapping a graph to a particular isomorph is just the size of its automorphism group? $\endgroup$– Gordon RoyleCommented Aug 13, 2016 at 23:35
-
$\begingroup$ @GordonRoyle may be I am confused in terms. can $\big|\{P\in S_n:PAP'=B\}\big|\geq n^{c'n}\gg n^c\geq\big|\{P\in S_n:PAP'=A\}\big|$ hold where $A$ is adjacency matrix of $G$ and $B$ is adjacency matrix of graph isomorphic to $G$ and $P\in S_n$ implies $P$ is a permutation matrix? $\endgroup$– TurboCommented Aug 13, 2016 at 23:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Vacuously, you can get this by having no two elements of the family isomorphic. If we add requirements implying that the family have lots of isomorphic elements (e.g. that the family be closed under isomorphism), then of course this is impossible by Gordon Royle's comment.
In more detail, to show that $Iso(G, H)$ has the same cardinality as $Aut(G)$, consider the map $$F: Iso(G, H)\rightarrow Aut(G): f\mapsto g\circ f,$$ where $g$ is a fixed element of $Iso(H, G)$. It's easy to show that $F$ is a bijection between $Iso(G, H)$ and $Aut(G)$.
answered Aug 13, 2016 at 23:58