Excluded permutation matrices and the Stanley-Wilf conjecture
From MaRDI portal
Publication:598446
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
Related Items
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, Extremal functions of excluded tensor products of permutation matrices, Ordered and convex geometric trees with linear extremal function, The structure of almost all graphs in a hereditary property, Shadows of ordered graphs, Repetition in reduced decompositions, On the likelihood of single-peaked preferences, Tight bounds on the maximum size of a set of permutations with bounded VC-dimension, Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns, Sharper bounds and structural results for minimally nonlinear 0-1 matrices, Grid classes and partial well order, Universal limits of substitution-closed permutation classes, On the sub-permutations of pattern avoiding permutations, Linear algebra methods for Forbidden configurations, Permutations generated by stacks and deques, Forbidden configurations and product constructions, Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices, Growth rates of geometric grid classes of permutations, Set families with forbidden subposets, Large deviations for permutations avoiding monotone patterns, Forbidden paths and cycles in ordered graphs and matrices, Countable linear orders with disjoint infinite intervals are mutually orthogonal, Forbidden Berge hypergraphs, On grids in topological graphs, A tournament approach to pattern avoiding matrices, An improvement of the general bound on the largest family of subsets avoiding a subposet, An algorithm computing combinatorial specifications of permutation classes, On the growth of merges and staircases of permutation classes, Partitioning ordered hypergraphs, Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts, Supercritical sequences, and the nonrationality of most principal permutation classes, On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Asymptotic enumeration of permutations avoiding generalized patterns, The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns, Avoiding consecutive patterns in permutations, Intervals of permutation class growth rates, On an extremal problem for poset dimension, On the structure of matrices avoiding interval-minor patterns, Linear bounds on matrix extremal functions using visibility hypergraphs, On linear forbidden submatrices, On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture, Finding and counting permutations via CSPs, A note on a Ramsey-type problem for sequences, On Stanley-Wilf limit of the pattern 1324, Variations on twins in permutations, Linear bound on extremal functions of some forbidden patterns in 0-1 matrices, Forbidden subposet problems in the grid, Restricted \(k\)-ary words and functional equations, Orthogonal countable linear orders, Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings, Pattern occurrences in \(k\)-ary words revisited: a few new and old observations, Extremal functions of forbidden double permutation matrices, A decorated tree approach to random permutations in substitution-closed classes, On 0-1 matrices and small excluded submatrices, Twin-width and polynomial kernels, Kernelization lower bound for permutation pattern matching, Inflations of geometric grid classes of permutations, A new record for \(1324\)-avoiding permutations, The feasible regions for consecutive patterns of pattern-avoiding permutations, On the topology of the permutation pattern poset, Asymptotic behaviour of the containment of certain mesh patterns
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Davenport-Schinzel theory of matrices
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
- The maximum number of unit distances in a convex \(n\)-gon
- Asymptotic values for degrees associated with strips of Young diagrams
- On the number of permutations avoiding a given pattern
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- Forbidden paths and cycles in ordered graphs and matrices
- An Extremal Problem on Sparse 0-1 Matrices
