Pattern Avoidance Over a Hypergraph

Abstract

A classic result of Marcus and Tardos (previously known as the Stanley-Wilf conjecture) bounds from above the number of $n$-permutations ($\sigma \in S_n$) that do not contain a specific sub-permutation. In particular, it states that for any fixed permutation $\pi$, the number of $n$-permutations that avoid $\pi$ is at most exponential in $n$. In this paper, we generalize this result. We bound the number of avoidant $n$-permutations even if they only have to avoid $\pi$ at specific indices. We consider a $k$-uniform hypergraph $\Lambda$ on $n$ vertices and count the $n$-permutations that avoid $\pi$ at the indices corresponding to the edges of $\Lambda$. We analyze both the random and deterministic hypergraph cases. This problem was originally proposed by Asaf Ferber.

When $\Lambda$ is a random hypergraph with edge density $\alpha$, we show that the expected number of $\Lambda$-avoiding $n$-permutations is bounded (both upper and lower) as $\exp(O(n))\alpha^{-\frac{n}{k-1}}$, using a supersaturation version of F\"{u}redi-Hajnal.

In the deterministic case we show that, for $\Lambda$ containing many size $L$ cliques, the number of $\Lambda$-avoiding $n$-permutations is $O\left(\frac{n\log^{2+\epsilon}n}{L}\right)^n$, giving a nontrivial bound with $L$ polynomial in $n$. Our main tool in the analysis of this deterministic case is the new and revolutionary hypergraph containers method, developed in papers of Balogh-Morris-Samotij and Saxton-Thomason.