Linear bounds on matrix extremal functions using visibility hypergraphs
From MaRDI portal
Publication:2515587
DOI10.1016/j.disc.2015.06.017zbMath1318.05048arXiv1410.3147OpenAlexW1559779571MaRDI QIDQ2515587
Publication date: 5 August 2015
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.3147
Extremal problems in graph theory (05C35) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Almost all permutation matrices have bounded saturation functions ⋮ Forbidden formations in multidimensional 0-1 matrices
Cites Work
- Degrees of nonlinearity in forbidden 0-1 matrix problems
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
- Extremal functions of forbidden double permutation matrices
- Davenport-Schinzel theory of matrices
- The maximum number of unit distances in a convex \(n\)-gon
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
- Bar k-Visibility Graphs
- Unnamed Item
This page was built for publication: Linear bounds on matrix extremal functions using visibility hypergraphs