Pattern avoidance over a hypergraph

DOI10.37236/9014MaRDI QIDQ2121745zbMATH OpenOpenAlexFDO

Authors Benjamin Gunby, Maxwell Fishelson

Publication date 4 April 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.09659

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Abstract: We consider the problem of bounding the number of permutations $sigmain{S}_n$ that avoid a fixed permutation $piin{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"uredi-Hajnal, which may be of independent interest.

Recommendations

• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• Fast Sorting and Pattern-Avoiding Permutations
• Excluded permutation matrices and the Stanley-Wilf conjecture
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• On the number of permutations avoiding a given pattern

Cites work

• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• Davenport-Schinzel theory of matrices
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Hypergraph containers
• Independent sets in hypergraphs
• Supersaturated sparse graphs and hypergraphs
• The number of \(C_{2\ell}\)-free graphs

Cited in

(2)

• Multiple pattern avoidance with respect to fixed points and excedances
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs

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)