Pattern avoidance over a hypergraph

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

\(k\)-uniform hypergraph hypergraph containers method Stanley-Wilf conjecture

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16) Hypergraphs (05C65)

Abstract: We consider the problem of bounding the number of permutations

s i g m a i n S_{n}

that avoid a fixed permutation

p i i n S_{k}

in specific indices given by a

k

-uniform hypergraph

L a m b d a

. We obtain relatively sharp bounds in the case where

L a m b d a

is a random hypergraph, and find bounds in the case where

L a m b d a

contains many large cliques. Along the way, we prove a supersaturation version of F"uredi-Hajnal, which may be of independent interest.

Review text

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)].

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Pattern avoidance over a hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2121745)