A Permutation Avoidance Game with Reverse Replies and Monotone Traps
This work addresses combinatorial game theory problems for researchers in discrete mathematics, focusing on pattern avoidance and winning strategies, but it is incremental as it builds on known concepts with specific extensions.
The paper tackles the impartial game PAP, where players avoid patterns, by defining a minimal monotone-forcing subset B_k of permutations and proving a quadratic upper bound for the monotone-forcing threshold, with exact thresholds determined for k=3,4,5,6. It shows that a reverse-reply strategy wins PAP for k=4 when n≥10 and for k=3, conjecturing it works for all large k and n.
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.