Degrees of nonlinearity in forbidden 0-1 matrix problems
From MaRDI portal
Publication:409347
DOI10.1016/j.disc.2011.06.020zbMath1239.05028MaRDI 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
05B20: Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05A05: Permutations, words, matrices
05D10: Ramsey theory
Related Items
Saturation Problems about Forbidden 0-1 Submatrices, Unnamed Item, On the Turán number of ordered forests, On the Turán number of ordered forests, An exact characterization of saturation for permutation matrices, On the union complexity of diametral disks, Tight bounds on the maximum size of a set of permutations with bounded VC-dimension, Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts, Almost all permutation matrices have bounded saturation functions, Bounds on parameters of minimally nonlinear patterns, Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices, On the structure of matrices avoiding interval-minor patterns, Ordered and convex geometric trees with linear extremal function, Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices, Forbidden formations in multidimensional 0-1 matrices, Linear bounds on matrix extremal functions using visibility hypergraphs, A relationship between generalized Davenport-Schinzel sequences and interval chains, Bipartite Turán problems for ordered graphs, Turán problems for edge-ordered graphs, Three Generalizations of Davenport--Schinzel Sequences
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
