Excluded permutation matrices and the Stanley-Wilf conjecture

DOI10.1016/J.JCTA.2004.04.002zbMATH Open1051.05004DBLPjournals/jct/MarcusT04OpenAlexW2091015960WikidataQ56815790 ScholiaQ56815790MaRDI QIDQ598446FDOQ598446

Authors: Gábor Tardos, Adam W. Marcus 

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

Recommendations

• Permutation classes and polyomino classes with excluded submatrices
• Extremal functions of excluded tensor products of permutation matrices
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Posets of matrices and permutations with forbidden subsequences
• On the number of mutually disjoint pairs of \(S\)-permutation matrices
• A conjecture of Stanley on alternating permutations
• Permutation matrices and beyond: an essay
• Matrices with restricted entries and \(q\)-analogues of permutations
• Permutation polynomials: A matrix analogue of Schur's conjecture and a survey of recent results
• scientific article; zbMATH DE number 6683614

zbMATH Keywords

Extremal problemsForbidden submatricesPattern avoidanceStanley-Wilf conjecture

Mathematics Subject Classification ID

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

Cites Work

• Davenport-Schinzel theory of matrices
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• Asymptotic values for degrees associated with strips of Young diagrams
• Forbidden paths and cycles in ordered graphs and matrices
• Title not available (Why is that?)
• On the number of permutations avoiding a given pattern
• The maximum number of unit distances in a convex \(n\)-gon
• Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
• Title not available (Why is that?)
• An Extremal Problem on Sparse 0-1 Matrices
• Title not available (Why is that?)
• The solution of a conjecture of Stanley and Wilf for all layered patterns
• Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences

Cited In (only showing first 100 items - show all)

• Large homogeneous submatrices
• Bounded affine permutations. II: Avoidance of decreasing patterns
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• An exact characterization of saturation for permutation matrices
• Saturation of Multidimensional 0-1 Matrices
• On the Turán number of ordered forests
• Variations on Hammersley’s interacting particle process
• Almost all permutation matrices have bounded saturation functions
• Spherical Schubert varieties and pattern avoidance
• An elementary proof of Bevan's theorem on the growth of grid classes of permutations
• Interval minors of complete bipartite graphs
• On the likelihood of single-peaked preferences
• Counting the nontrivial equivalence classes of \(S_n\) under \(\{1234, 3412\}\)-pattern-replacement
• Forbidden induced subposets of given height
• Supercritical sequences, and the nonrationality of most principal permutation classes
• Title not available (Why is that?)
• On an extremal problem for poset dimension
• Bounds on parameters of minimally nonlinear patterns
• Pattern avoidance over a hypergraph
• Variations on twins in permutations
• Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
• Pattern occurrences in \(k\)-ary words revisited: a few new and old observations
• Intervals of permutation class growth rates
• Universal limits of substitution-closed permutation classes
• Blockers of pattern avoiding permutation matrices
• Extremal problems for ordered hypergraphs: small patterns and some enumeration
• Title not available (Why is that?)
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• On pattern avoidance in matchings and involutions
• On the Turán number of ordered forests
• Bipartite Turán problems for ordered graphs
• On Stanley-Wilf limit of the pattern 1324
• Extremal functions of forbidden multidimensional matrices
• Forbidden formations in multidimensional 0-1 matrices
• Linear bounds on matrix extremal functions using visibility hypergraphs
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• A note on a Ramsey-type problem for sequences
• Finding and counting permutations via CSPs
• Word-Representable Graphs: a Survey
• Universality of random permutations
• On the structure of matrices avoiding interval-minor patterns
• Partitioning ordered hypergraphs
• Permutations avoiding 1324 and patterns in Łukasiewicz paths
• A note on permutation regularity
• Extremal problems for convex geometric hypergraphs and ordered hypergraphs
• A decorated tree approach to random permutations in substitution-closed classes
• Staircases, dominoes, and the growth rate of 1324-avoiders
• Countable linear orders with disjoint infinite intervals are mutually orthogonal
• Linear algebra methods for Forbidden configurations
• Better upper bounds on the Füredi-Hajnal limits of permutations
• A LYM inequality for induced posets
• On the growth of merges and staircases of permutation classes
• Forbidden subposet problems in the grid
• Title not available (Why is that?)
• A new record for \(1324\)-avoiding permutations
• Combinatorial properties of poly-Bernoulli relatives
• Bounded affine permutations. I: Pattern avoidance and enumeration
• The length of an s-increasing sequence of r-tuples
• On permutation patterns with constrained gap sizes
• Avoiding consecutive patterns in permutations
• Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths
• Geometric grid classes of permutations
• Pairs of orthogonal countable ordinals
• Using functional equations to enumerate 1324-avoiding permutations
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
• Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
• On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• Inflations of geometric grid classes of permutations
• Permutations with partially forbidden positions.
• The structure of almost all graphs in a hereditary property
• Reconstruction of matrices from submatrices
• Kernelization lower bound for permutation pattern matching
• Pattern avoidance in ordered set partitions
• Extremal functions of excluded tensor products of permutation matrices
• On grids in topological graphs
• Counting ordered graphs that avoid certain subgraphs
• Locally convex words and permutations
• On the topology of the permutation pattern poset
• Tilings in vertex ordered graphs
• On linear forbidden submatrices
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Extremal functions of forbidden double permutation matrices
• On the Turán number of some ordered even cycles
• Waiting time distribution for the emergence of superpatterns
• Repetition in reduced decompositions
• Longest alternating subsequences of permutations
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• A new upper bound for 1324-avoiding permutations
• Large deviations and ratio limit theorems for pattern-avoiding permutations
• Restricted \(k\)-ary words and functional equations
• The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• On scattered convex geometries
• Asymptotic enumeration of permutations avoiding generalized patterns
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• New records in Stanley-Wilf limits
• Counting pattern-free set partitions. II: Noncrossing and other hypergraphs
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture

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

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