Rigidity of Pattern-Avoiding Breadth-First Reading Words of Increasing Trees
Victor Bona
We study permutations obtained by reading increasing ordered trees in breadth-first order. For every integer k >= 2, a 312-avoiding permutation is realizable on a tree of maximum outdegree k if and only if it is realizable on the complete k-ary heap shape. A 231-avoiding permutation of length congruent to 1 modulo k is realizable with maximum outdegree k if and only if it is realizable on a full k-ary tree. Both proofs use the nondecreasing sequence of BFS parent positions. The binary specializations prove three identities between OEIS sequences, including A245899 = A246747. For 321, heap collapse first fails at length 4, while full binary collapse first fails at odd length 11, with 8095 unary-binary words and 8048 full binary words. The artifact supplies 28 additional sequence entries relative to the recorded baseline, the complete 47-word counterexample set, executable enumeration and verification programs, and Lean 4 proofs. The binary results are formalized on inductive trees; the arbitrary-k arguments are formalized over parent sequences. Exponential growth rate 4 follows from Defant's heap-growth theorem.