For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.

Is it true that $\mathcal {P}_n$ has no nontrivial automorphisms?


This follows if one can recognize a graph from the set of isomorphism classes of its edge-deleted subgraphs. However, since recognizing a graph from the set of isomorphism classes of its edge-deleted subgraphs is stronger than edge reconstruction, I'm wondering if there is an alternative way of proving this.

  • 1
    $\begingroup$ Maybe it is useful to add that $\cal P_4$ has a nontrivial automorphism. Did you ckeck for higher values, e.g. using the tables from maths.uq.edu.au/~pa/research/posets4to8.html? $\endgroup$ – domotorp Dec 31 '13 at 5:46
  • $\begingroup$ $\mathcal P_5$ can pretty easily be checked by hand. As for anything larger, I'm not sure. $\endgroup$ – Wade Hann-Caruthers Dec 31 '13 at 6:30
  • $\begingroup$ Of course there is in fact no need to check, as it anyhow follows from the set edge reconstruction conjecture but I could not find anything about for what values that has been checked. $\endgroup$ – domotorp Dec 31 '13 at 11:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.