Pattern Avoidance Over a Hypergraph

Abstract

We consider the problem of bounding the number of permutations $\sigma \in S_n$ that avoid a fixed permutation $\pi \in S_k$ in specific indices given by a $k$-uniform hypergraph $\Lambda$. We obtain relatively sharp bounds in the case where $\Lambda$ is a random hypergraph, and find bounds in the case where $\Lambda$ contains many large cliques. Along the way, we prove a supersaturation version of Füredi-Hajnal, which may be of independent interest.

arXiv comment33 pages. v2, some restructuring and edits made for clarity. Added a discussion about concentration results