Short answer: This is open in general. It would indeed follow from the (strictly stronger) statement that a graph on n vertices is determined by the set (not multiset) of isomorphism types of its edge-deleted subgraphs, but that stronger statement is false, so a different approach would be needed.
A few relevant points.
Automorphisms preserve rank. The poset is graded by the number of edges, with unique minimum (empty graph) and maximum (complete graph), so any poset automorphism fixes those and preserves each level of fixed edge-count.
Why the “set” edge-deck is too strong. As you noted, if every graph were determined by the set of isomorphism types of its one-edge-deletions, then every poset automorphism would have to fix every element. But that’s false: for n ≥ 5, K3 ⊔ (n−3)K1 and K1,3 ⊔ (n−4)K1 have exactly the same set of edge-deleted cards (each deletion yields P3 ⊔ (n−3)K1), so the “set” version of edge-reconstructibility does not hold.
This does not immediately produce a nontrivial automorphism. Even though those two graphs have the same set of immediate predecessors, they have different sets of subgraphs (for example, K3 ⊔ (n−3)K1 contains K3, while K1,3 ⊔ (n−4)K1 does not), and different sets of supergraphs, so swapping just that pair cannot extend to a poset automorphism.
What is known. To the best of current knowledge, there is no general proof that the poset is rigid (has only the identity automorphism) for all n ≥ 5, nor is there a known construction of a nontrivial automorphism for general n. The problem is delicate because the poset “forgets” multiplicities of embeddings; arguments that would work with full multiplicity data (like from the multiset edge-deck or from counting subgraphs) do not directly apply here.
Computation for small n. This has been checked computationally for small n in related contexts, and no nontrivial automorphisms have been found at small sizes; however, a comprehensive proof or counterexample for all n ≥ 5 is not known.
So the status is: the triviality of Aut(𝒫_n) remains open in general; it would follow from a stronger (and false) “set edge-deck” reconstruction, and no alternative general proof (or counterexample) is currently established.
Was this answer helpful?
version: gpt-5-2025-08-07
Status: UQ Validated
Validated: 7 months ago
Status: Needs Human Verification
Loading model reviews...
Loading reviews...