Suppose we have a finite set $A$ and a partial order on its subsets--i.e. a poset. Draw the directed Hasse diagram: that is, for elements $a$ and $b$ in the powerset of $A$ we draw $a \to b$ if $a \leq b$.

My conjecture is that the graph automorphisms (which preserve direction of edges) of any Hasse diagram is the product of symmetric groups. I.e. For any poset $P$ with Hasse diagram $H$ we have $Aut(H) = S_{n_1} \times S_{n_2} \times \cdots \times S_{n_k}$.

Example: Take the poset that is set inclusion on the powerset $P(A)$ for $A$ finite. This is a |A|-dimensional hypercube. The Hasse diagram is preserved by permuting elements of $A$.

Is this true in general?

  • $\begingroup$ Are the graph automorphisms the same as the order isomorphisms of the poset? $\endgroup$ – William Elliot Mar 26 '18 at 21:46
  • $\begingroup$ I am a little out of my depth here but I believe so. $\endgroup$ – abnry Mar 26 '18 at 21:48
  • $\begingroup$ If (a,b) is permuted to (b,a) how is the directed diagram not altered? $\endgroup$ – William Elliot Mar 26 '18 at 21:49
  • $\begingroup$ What does $(a,b)$ represent here? Isn't an order isomorphism $f$ such that if $a \leq b$ then $f(a) \leq f(b)$? $\endgroup$ – abnry Mar 26 '18 at 21:52
  • $\begingroup$ What are $n_{1}$, $n_{2}$, $\ldots$, $n_{k}$? Are these the sizes of the levels of the Hasse diagram? Your automorphism group will be a subgroup of the direct product of symmetric groups you have written, but will certainly not be isomorphic (unless you have all possible edges between levels). $\endgroup$ – Morgan Rodgers Mar 26 '18 at 22:11

No this is not true if you allow arbitrary partial orderings. If you take the Hasse diagram on the collection of subspaces of $\mathbb{F}_{q}^{n}$, the automorphism group will be $\mathrm{P\Gamma L}(n,q)$ which cannot be represented as a direct product of symmetric groups. This can be represented in the terms you give as all subspaces are collections of vectors, and the collection of vectors is a finite set. Any subset that does not correspond to a subspace can be declared incomparable with the rest.

Also note that, in general, the automorphism group of a Hasse diagram is not necessarily determined by its permutation action on the elements at a fixed level. It is a permutation group on all of the elements of the diagram.

The example you give, $P(A)$ for some finite set $A$, is especially nicely behaved. This is an example of a lattice, where every pair of elements has a meet and a join. It has a natural base set (the collection of one-element subsets) which can be used to describe all of the other elements, and so an automorphism of the diagram can be described in terms of the action on this base set. And for this particular example, any permutation of these elements can be extended to an automorphism of the diagram. But this is a special property of the particular structure you are looking at.

  • $\begingroup$ Thank you for your answer, you've given me some things to chew on. Can you fill in detail for your example of the subspace of $F_q^n$? For $F_2^2$ we actually have $S_3$ as the set of graph automorphisms of the poset of subspaces. But that is probably an artifact of small $n$ and $q$. I do not understand why the projective linear group are the graph automorphisms either. $\endgroup$ – abnry Mar 27 '18 at 17:58
  • $\begingroup$ A graph automorphism of the Hasse diagram is not determined by its permutation action on the elements at each level, but elements from each level must be mapped to elements within the same level. As if $a \leq b \leq c$ has no intermediate element between comparisons and $a \leq x$ for any comparable $x$, then $f(a) \leq f(b) \leq f(c)$ must also hold. So the level of $c$ is at least 3. But consider $f^{-1}$ to get it exactly 3. $\endgroup$ – abnry Mar 27 '18 at 18:01
  • $\begingroup$ My conjecture came from not being able to find any examples otherwise, not from thinking about the action on the levels. But perhaps I am not sure about the differences between lattices and hasse diagrams, and my examples were only lattices. $\endgroup$ – abnry Mar 27 '18 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.