An Extremal Problem on Sparse 0-1 Matrices

DOI10.1137/0404002zbMath0752.05012OpenAlexW1994055767MaRDI QIDQ3971234

Bienstock, Daniel, Ervin Gyoeri

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)

Related Items (22)

An exact characterization of saturation for permutation matrices ⋮ Saturation of Multidimensional 0-1 Matrices ⋮ Almost all permutation matrices have bounded saturation functions ⋮ On the maximum density of 0-1 matrices with no forbidden rectangles ⋮ Interval Minors of Complete Bipartite Graphs ⋮ Excluded permutation matrices and the Stanley-Wilf conjecture ⋮ Extremal functions of forbidden multidimensional matrices ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Ordered and convex geometric trees with linear extremal function ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ Davenport-Schinzel theory of matrices ⋮ Forbidden paths and cycles in ordered graphs and matrices ⋮ Partitioning ordered hypergraphs ⋮ On forbidden submatrices ⋮ On the structure of matrices avoiding interval-minor patterns ⋮ On linear forbidden submatrices ⋮ A near-linear algorithm for the planar segment-center problem ⋮ Linear bound on extremal functions of some forbidden patterns in 0-1 matrices ⋮ Extremal functions of forbidden double permutation matrices ⋮ On 0-1 matrices and small excluded submatrices ⋮ Unnamed Item

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