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

DOI10.1016/j.disc.2008.02.040zbMath1193.05043OpenAlexW2080876227MaRDI QIDQ1024495

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

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

Related Items (8)

An exact characterization of saturation for permutation matrices ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Generalized Davenport-Schinzel sequences and their 0-1 matrix counterparts ⋮ 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 ⋮ Extremal functions of forbidden double permutation matrices

Cites Work

• Unnamed Item
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Representing a planar graph by vertical lines joining different levels
• A unified approach to visibility representations of planar graphs
• Davenport-Schinzel theory of matrices
• Generalized Davenport-Schinzel sequences
• The maximum number of unit distances in a convex \(n\)-gon
• On 0-1 matrices and small excluded submatrices
• An Extremal Problem on Sparse 0-1 Matrices
• Forbidden patterns and unit distances

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