Degrees of nonlinearity in forbidden 0-1 matrix problems
From MaRDI portal
Publication:409347
DOI10.1016/j.disc.2011.06.020zbMath1239.05028OpenAlexW2025410851MaRDI QIDQ409347
Publication date: 13 April 2012
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2011.06.020
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Permutations, words, matrices (05A05) Ramsey theory (05D10)
Related Items
An exact characterization of saturation for permutation matrices, Almost all permutation matrices have bounded saturation functions, Three Generalizations of Davenport--Schinzel Sequences, On the union complexity of diametral disks, Bipartite Turán problems for ordered graphs, Forbidden formations in multidimensional 0-1 matrices, Bounds on parameters of minimally nonlinear patterns, Ordered and convex geometric trees with linear extremal function, Turán problems for edge-ordered graphs, Tight bounds on the maximum size of a set of permutations with bounded VC-dimension, Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices, Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices, Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts, On the Turán number of ordered forests, On the Turán number of ordered forests, On the structure of matrices avoiding interval-minor patterns, Linear bounds on matrix extremal functions using visibility hypergraphs, Saturation Problems about Forbidden 0-1 Submatrices, A relationship between generalized Davenport-Schinzel sequences and interval chains, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- On linear forbidden submatrices
- Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
- Extremal functions of forbidden double permutation matrices
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Davenport-Schinzel theory of matrices
- Generalized Davenport-Schinzel sequences with linear upper bound
- Norm-graphs: Variations and applications
- Generalized Davenport-Schinzel sequences
- The maximum number of unit distances in a convex \(n\)-gon
- Explicit construction of graphs with an arbitrary large girth and of large size
- On the number of permutations avoiding a given pattern
- Forbidden paths and cycles in ordered graphs and matrices
- On 0-1 matrices and small excluded submatrices
- Origins of Nonlinearity in Davenport–Schinzel Sequences
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- New lower bound techniques for VLSI
- Crossing-Free Subgraphs
- An Extremal Problem on Sparse 0-1 Matrices
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
- Extremal Graphs without Large Forbidden Subgraphs
- A new series of dense graphs of high girth
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- An Upper Bound on Zarankiewicz' Problem
- On the structure and composition of forbidden sequences, with geometric applications
- On Graphs that do not Contain a Thomsen Graph
- On a problem of K. Zarankiewicz
