Rigidity of Pattern-Avoiding Breadth-First Reading Words of Increasing Trees

$ cat abstract

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.

$ ls index-terms/

enumerative combinatoricspermutation patternsincreasing treesbreadth-first searchk-ary heapsOEISLean 4formal verificationreproducibility

@misc{bona2026bfsavoidance,
  author = {Victor Bona},
  title = {Rigidity of Pattern-Avoiding Breadth-First Reading Words of Increasing Trees},
  year = {2026},
  month = {sep},
  publisher = {Zenodo},
  doi = {10.5281/zenodo.23042420},
  url = {https://doi.org/10.5281/zenodo.23042420},
  note = {Preprint}
}