Long paths, deep trees and permutation pattern-counting

We study the counting problem known as #PPM, whose input is a pair of permutations \(\pi\) and \(\tau\) (called pattern and text, respectively), and the task is to find the number of subsequences of \(\tau\) that have the same relative order as \(\pi\). A simple brute-force approach solves #PPM for a pattern of length \(k\) and a text of length \(n\) in time \(\mathcal{O}(n^{k+1})\), while Berendsohn, Kozma and Marx have recently shown that under the Exponential time hypothesis (ETH), it cannot be solved in time \(f(k)n^{o(k/\log k)}\) for any function \(f\). In this talk, we consider the restriction of #PPM, known as \(\mathfrak{C}\)-Pattern #PPM, where the pattern \(\pi\) must belong to a hereditary permutation class \(\mathfrak{C}\). Our goal is to identify the structural properties of \(\mathfrak{C}\) that determine the complexity of \(\mathfrak{C}\)-Pattern #PPM. We focus on two such structural properties, known as the long path property (LPP) and the deep tree property (DTP). Assuming ETH, we obtain these results:

1. If \(\mathfrak{C}\) has the LPP, then \(\mathfrak{C}\)-Pattern #PPM cannot be solved in time \(f(k)n^{o(\sqrt{k})}\) for any function \(f\), and
2. if \(\mathfrak{C}\) has the DTP, then \(\mathfrak{C}\)-Pattern #PPM cannot be solved in time \(f(k)n^{o(k/\log^2 k)}\) for any function \(f\).

Furthermore, we investigate how the LPP and DTP influence the maximal tree-width attained by a permutation of length \(n\). We show that:

1. If \(\mathfrak{C}\) has the LPP, then \(\mathfrak{C}\) contains permutations of tree-width \(\Omega(\sqrt{n})\), and
2. if \(\mathfrak{C}\) has the DTP, then \(\mathfrak{C}\) contains permutations of tree-width \(\Omega(n/\log n)\).

This is joint work with Vít Jelínek and Jakub Pekárek.

Recording