The minimum size of a contiguous k-universal d-ary plane tree is exactly d^{k-1}+k-1; the noncontiguous variants have minimum sizes between roughly k log_2 k and k^{(1/2) log_2 k}.
Polyurethane Toggles
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We consider the involutions known as "toggles," which have been used to give simplified proofs of the fundamental properties of the promotion and evacuation maps. We transfer these involutions so that they generate a group $\mathscr P_n$ that acts on the set $S_n$ of permutations of $\{1,\ldots,n\}$. After characterizing its orbits in terms of permutation skeletons, we apply the action in order to understand West's stack-sorting map. We obtain a very simple proof of a result that clarifies and extensively generalizes a theorem of Bouvel and Guibert and also generalizes a theorem of Bousquet-M\'elou. We also settle a conjecture of Bouvel and Guibert. We prove a result related to the recently-introduced notion of postorder Wilf equivalence. Finally, we investigate an interesting connection among the action of $\mathscr P_n$ on $S_n$, the group structure of $S_n$, and the stack-sorting map.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Supertrees
The minimum size of a contiguous k-universal d-ary plane tree is exactly d^{k-1}+k-1; the noncontiguous variants have minimum sizes between roughly k log_2 k and k^{(1/2) log_2 k}.