An Extremal Problem on Sparse 0-1 Matrices

DOI10.1137/0404002MaRDI QIDQ3971234zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock, Ervin Győri

Publication date 25 June 1992

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0404002

zbMATH Keywords

trapezoidextremal problemsparse 0-1 matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05)

Recommendations

• An extremal problem concerning matrices of 0's and 1 's
• On the determinant of a sparse 0-1 matrix
• Maximum determinant and permanent of sparse 0-1 matrices
• On very sparse circulant \((0,1)\) matrices
• On two extremal matrix problems
• Extermal positive semidefinite matrices with given sparsity pattern
• Some extremal problems concerning the square of a (0,1)-matrix
• Sparse 0−1 Matrices and Forbidden Hypergraphs

Cited in

(28)

• An extremal problem concerning matrices of 0's and 1 's
• 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
• Saturation of Multidimensional 0-1 Matrices
• Interval minors of complete bipartite graphs
• On linear forbidden submatrices
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Extremal functions of forbidden double permutation matrices
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• scientific article; zbMATH DE number 7053339 (Why is no real title available?)
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Ordered and convex geometric trees with linear extremal function
• On the determinant of a sparse 0-1 matrix
• On the maximum density of 0-1 matrices with no forbidden rectangles
• scientific article; zbMATH DE number 1303555 (Why is no real title available?)
• Davenport-Schinzel theory of matrices
• On the staircases of Gyárfás
• Extremal functions of forbidden multidimensional matrices
• On forbidden submatrices
• On 0-1 matrices and small excluded submatrices
• On the structure of matrices avoiding interval-minor patterns
• Partitioning ordered hypergraphs
• A near-linear algorithm for the planar segment-center problem
• Extremal bounds for pattern avoidance in multidimensional 0-1 matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Sparse 0−1 Matrices and Forbidden Hypergraphs
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

This page was built for publication: An Extremal Problem on Sparse 0-1 Matrices

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