Excluded permutation matrices and the Stanley-Wilf conjecture

DOI10.1016/j.jcta.2004.04.002zbMath1051.05004OpenAlexW2091015960WikidataQ56815790 ScholiaQ56815790MaRDI QIDQ598446

Publication date: 6 August 2004

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2004.04.002

zbMATH Keywords

Extremal problems Forbidden submatrices Pattern avoidance Stanley-Wilf conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Related Items (only showing first 100 items - show all)

The length of an s-increasing sequence of r-tuples ⋮ An exact characterization of saturation for permutation matrices ⋮ Saturation of Multidimensional 0-1 Matrices ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Twin-width II: small classes ⋮ Variations on Hammersley’s interacting particle process ⋮ Interview with Bruce Sagan ⋮ Fast Property Testing and Metrics for Permutations ⋮ Interval Minors of Complete Bipartite Graphs ⋮ A New Upper Bound for 1324-Avoiding Permutations ⋮ Word-Representable Graphs: a Survey ⋮ A generalization of the K\H{o}v\'{a}ri-S\'{o}s-Tur\'{a}n theorem ⋮ Permutations avoiding 1324 and patterns in Łukasiewicz paths ⋮ Graphs of bounded twin-width are quasi-polynomially $\chi $-bounded ⋮ Rectilinear approximation and volume estimates for hereditary bodies via [0, 1‐decorated containers] ⋮ An Algorithm to Enumerate Grid Signed Permutation Classes ⋮ Permutations avoiding a pattern of length three under Mallows distributions ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations ⋮ Hereditary classes of ordered binary structures ⋮ Stanley-Wilf limits for patterns in rooted labeled forests ⋮ Logical limit laws for layered permutations and related structures ⋮ Preface to the special issue of Permutation Patterns 2021 (PP2021) ⋮ Unnamed Item ⋮ Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations ⋮ A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs ⋮ The design of efficient dynamic programming and transfer matrix enumeration algorithms ⋮ Turán problems for edge-ordered graphs ⋮ Forbidden Hypermatrices Imply General Bounds on Induced Forbidden Subposet Problems ⋮ Permutation classes and polyomino classes with excluded submatrices ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Universality of random permutations ⋮ Growing at a Perfect Speed ⋮ Bounded affine permutations I. Pattern avoidance and enumeration ⋮ Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations ⋮ A note on permutation regularity ⋮ Pattern‐avoiding permutations and Brownian excursion part I: Shapes and fluctuations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reconstruction of matrices from submatrices ⋮ Unnamed Item ⋮ On the Turán number of ordered forests ⋮ A note on permutation regularity ⋮ On the Turán number of ordered forests ⋮ Combinatorial properties of poly-Bernoulli relatives ⋮ Counting the Nontrivial Equivalence Classes of $S_n$ under $\{1234,3412\}$-Pattern-Replacement ⋮ Saturation Problems about Forbidden 0-1 Submatrices ⋮ An Elementary Proof of Bevan's Theorem on the Growth of Grid Classes of Permutations ⋮ PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188 ⋮ Geometric grid classes of permutations ⋮ Quasi-planar Graphs ⋮ Growth rates of permutation grid classes, tours on graphs, and the spectral radius ⋮ Large Homogeneous Submatrices ⋮ Unnamed Item ⋮ Extremal problems for convex geometric hypergraphs and ordered hypergraphs ⋮ On the centrosymmetric permutations in a class ⋮ Pattern avoidance over a hypergraph ⋮ On pattern avoidance in matchings and involutions ⋮ Bounded affine permutations. II: Avoidance of decreasing patterns ⋮ Counting ordered graphs that avoid certain subgraphs ⋮ Forbidden induced subposets of given height ⋮ Locally convex words and permutations ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Spherical Schubert varieties and pattern avoidance ⋮ Extremal problems for pairs of triangles ⋮ Tilings in vertex ordered graphs ⋮ Waiting time distribution for the emergence of superpatterns ⋮ Extremal problems for ordered hypergraphs: small patterns and some enumeration ⋮ Longest alternating subsequences of permutations ⋮ Hereditary properties of partitions, ordered graphs and ordered hypergraphs ⋮ New records in Stanley-Wilf limits ⋮ Extensions of the linear bound in the Füredi-Hajnal conjecture ⋮ Permutations sortable by two stacks in series ⋮ Classical length-5 pattern-avoiding permutations ⋮ On the Turán number of some ordered even cycles ⋮ Extremal functions of forbidden multidimensional matrices ⋮ $k$-pop stack sortable permutations and $2$-avoidance ⋮ The poset of mesh patterns ⋮ Patterns in random permutations ⋮ Improved enumeration of simple topological graphs ⋮ Longest monotone subsequences and rare regions of pattern-avoiding permutations ⋮ A probabilistic approach to consecutive pattern avoiding in permutations ⋮ Growth rates of permutation classes: categorization up to the uncountability threshold ⋮ Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths ⋮ On scattered convex geometries ⋮ Pairs of orthogonal countable ordinals ⋮ Using functional equations to enumerate 1324-avoiding permutations ⋮ Bipartite Turán problems for ordered graphs ⋮ Pattern avoidance in ordered set partitions ⋮ A structural characterisation of $\mathrm{Av}(1324)$ and new bounds on its growth rate ⋮ A LYM inequality for induced posets ⋮ Staircases, dominoes, and the growth rate of 1324-avoiders ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems

Cites Work

This page was built for publication: Excluded permutation matrices and the Stanley-Wilf conjecture