A permutation avoidance game with reverse replies and monotone traps

In preparation

Henning

Two block-size-4 one-entry inflation examples We study the impartial game PAP (permutations avoiding patterns), in which players take turns choosing patterns to avoid. We define a set of length \(k\) patterns, \(B_k\), and show that it is the unique minimal monotone-forcing subset of \(S_k\): every sufficiently long permutation that avoids \(B_k\) is monotone, and every monotone-forcing subset of \(S_k\) must contain \(B_k\). We prove a quadratic upper bound for the monotone-forcing threshold, and determine the exact thresholds for \(k=3,4,5,6\). We use properties of the sets \(B_k\) to prove that a reverse-reply strategy wins PAP on \(S_n\) when \(k=4\) for all \(n \geq 10\); for \(k=3\), the same strategy can be analysed directly. We conjecture that it is a winning strategy for all \(k\) and \(n\) sufficiently large.

Download the paper