The subalgebra of corner trees

Permutation patterns appear in a plethora of research areas, including statistics, combinatorics, algebra, geometry, and computer science. As an example, counting the number of occurrences of small patterns is relevant in nonparametric statistics. The naive counting algorithm has polynomial complexity with degree corresponding to the size of the pattern. Recent breakthrough work by Zohar et al. (2021) shows that some patterns can be counted in nearly linear time. To address the problem, Zohar introduced corner trees, finite rooted trees endowed with some additional data. To understand the subspace of permutations expressable by corner trees, we encode both corner trees and permutations as double posets, i.e. sets equipped with two partial order relations.

This approach seems beneficial since:

• various corner trees are the same double poset in disguise,
• we can use results from category theory that concern the factorization of morphisms. These factorizations yield immediate proofs of results appearing in the article by Zohar et al. (2021),
• we introduce a nearly quadratic algorithm to count a double poset which is almost a corner tree. This allows us to count all permutations up to level 4.

This is ongoing work with Joscha Diehl