Pattern avoidance over a hypergraph (Q2121745)

Summary: A classic result of \textit{A. Marcus} and \textit{G. Tardos} [J. Comb. Theory, Ser. A 107, No. 1, 153--160 (2004; Zbl 1051.05004)] (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 \textit{Z. Füredi} and \textit{P. Hajnal} [Discrete Math. 103, No. 3, 233--251 (1992; Zbl 0776.05024)]. 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 \textit{J. Balogh} et al. [J. Am. Math. Soc. 28, No. 3, 669--709 (2015; Zbl 1310.05154)] and \textit{D. Saxton} and \textit{A. Thomason} [Invent. Math. 201, No. 3, 925--992 (2015; Zbl 1320.05085)].