Degrees of nonlinearity in forbidden 0-1 matrix problems
From MaRDI portal
Publication:409347
DOI10.1016/J.DISC.2011.06.020zbMATH Open1239.05028OpenAlexW2025410851MaRDI QIDQ409347FDOQ409347
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
Recommendations
Permutations, words, matrices (05A05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Ramsey theory (05D10)
Cites Work
- \(L_ 1\) shortest paths among polygonal obstacles in the plane
- Title not available (Why is that?)
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- On Graphs that do not Contain a Thomsen Graph
- On a problem of K. Zarankiewicz
- Davenport-Schinzel theory of matrices
- Forbidden paths and cycles in ordered graphs and matrices
- Crossing-Free Subgraphs
- Title not available (Why is that?)
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
- Norm-graphs: Variations and applications
- Explicit construction of graphs with an arbitrary large girth and of large size
- A new series of dense graphs of high girth
- On the number of permutations avoiding a given pattern
- An Upper Bound on Zarankiewicz' Problem
- Title not available (Why is that?)
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
- The maximum number of unit distances in a convex \(n\)-gon
- 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
- Generalized Davenport-Schinzel sequences with linear upper bound
- Generalized Davenport-Schinzel sequences
- On 0-1 matrices and small excluded submatrices
- Origins of Nonlinearity in Davenport–Schinzel Sequences
- Title not available (Why is that?)
- New lower bound techniques for VLSI
- An Extremal Problem on Sparse 0-1 Matrices
- Extremal Graphs without Large Forbidden Subgraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the structure and composition of forbidden sequences, with geometric applications
- Title not available (Why is that?)
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
Cited In (26)
- On the union complexity of diametral disks
- An exact characterization of saturation for permutation matrices
- On the Turán number of ordered forests
- Out of Non-linearity: Search Impossible Differentials by the Bitwise Characteristic Matrix
- Almost all permutation matrices have bounded saturation functions
- Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
- Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
- Title not available (Why is that?)
- On an extremal problem for poset dimension
- On linear forbidden submatrices
- Bounds on parameters of minimally nonlinear patterns
- Lower bounds on Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
- Saturation Problems about Forbidden 0-1 Submatrices
- Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
- Ordered and convex geometric trees with linear extremal function
- Three Generalizations of Davenport--Schinzel Sequences
- On the Turán number of ordered forests
- Bipartite Turán problems for ordered graphs
- Davenport-Schinzel theory of matrices
- Forbidden formations in multidimensional 0-1 matrices
- Linear bounds on matrix extremal functions using visibility hypergraphs
- Turán problems for edge-ordered graphs
- On the structure of matrices avoiding interval-minor patterns
- Forbidden paths and cycles in ordered graphs and matrices
- A relationship between generalized Davenport-Schinzel sequences and interval chains
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
This page was built for publication: Degrees of nonlinearity in forbidden 0-1 matrix problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409347)
