Linear bounds on matrix extremal functions using visibility hypergraphs

DOI10.1016/j.disc.2015.06.017zbMath1318.05048arXiv1410.3147OpenAlexW1559779571MaRDI QIDQ2515587

Lilly Shen, Jesse T. Geneson

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

zbMATH Keywords

extremal functionspattern avoidancebar visibility graphsforbidden 0-1 matrices

Mathematics Subject Classification ID

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