Linear bound on extremal functions of some forbidden patterns in 0-1 matrices

DOI10.1016/J.DISC.2008.02.040MaRDI QIDQ1024495zbMATH OpenOpenAlexFDO

Authors Radoslav Fulek

Publication date 17 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.02.040

zbMATH Keywords

extremal problemspattern avoidanceforbidden submatriceslinear bounds

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Recommendations

• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• Linear bounds on matrix extremal functions using visibility hypergraphs
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
• Degrees of nonlinearity in forbidden 0-1 matrix problems

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A unified approach to visibility representations of planar graphs
• An Extremal Problem on Sparse 0-1 Matrices
• Davenport-Schinzel theory of matrices
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Forbidden patterns and unit distances
• Generalized Davenport-Schinzel sequences
• On 0-1 matrices and small excluded submatrices
• Representing a planar graph by vertical lines joining different levels
• The maximum number of unit distances in a convex n-gon

Cited in

(20)

• scientific article; zbMATH DE number 2186901 (Why is no real title available?)
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Almost all permutation matrices have bounded saturation functions
• An exact characterization of saturation for permutation matrices
• Avoiding Patterns in Matrices Via a Small Number of Changes
• Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts
• On linear forbidden submatrices
• Extremal functions of forbidden double permutation matrices
• Bounds on parameters of minimally nonlinear patterns
• Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
• On the maximum density of 0-1 matrices with no forbidden rectangles
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• Extremal functions of forbidden multidimensional matrices
• Forbidden formations in multidimensional 0-1 matrices
• Linear bounds on matrix extremal functions using visibility hypergraphs
• On nonlinear forbidden 0--1 matrices, a refutation of a Füredi-Hajnal conjecture
• Tight general bounds for the extremal numbers of 0-1 matrices
• On 0-1 matrices and small excluded submatrices
• On the structure of matrices avoiding interval-minor patterns
• Saturation problems about forbidden 0-1 submatrices

This page was built for publication: Linear bound on extremal functions of some forbidden patterns in 0-1 matrices

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