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 (20)
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
This page was built for publication: Degrees of nonlinearity in forbidden 0-1 matrix problems
