Linear bounds on matrix extremal functions using visibility hypergraphs

DOI10.1016/J.DISC.2015.06.017MaRDI QIDQ2515587zbMATH OpenOpenAlexFDO

Authors Lilly Shen, Jesse 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

bar visibility graphsextremal functionsforbidden 0-1 matricespattern avoidance

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: The 0-1 matrix A contains a 0-1 matrix M if some submatrix of A can be transformed into M by changing some ones to zeroes. If A does not contain M, then A avoids M. Let ex(n,M) be the maximum number of ones in an n x n 0-1 matrix that avoids M, and let ex_k(m,M) be the maximum number of columns in a 0-1 matrix with m rows that avoids M and has at least k ones in every column. A method for bounding ex(n,M) by using bounds on the maximum number of edges in bar visibility graphs was introduced in (R. Fulek, Discrete Mathematics 309, 2009). By using a similar method with bar visibility hypergraphs, we obtain linear bounds on the extremal functions of other forbidden 0-1 matrices.

Recommendations

• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• On 0-1 matrices and small excluded submatrices
• On linear forbidden submatrices
• Forbidden formations in multidimensional 0-1 matrices

Cites work

• Bar k-Visibility Graphs
• Davenport-Schinzel theory of matrices
• Degrees of nonlinearity in forbidden 0-1 matrix problems
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Extremal functions of forbidden double permutation matrices
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• The maximum number of unit distances in a convex n-gon
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

Cited in

(5)

• Linear bound on extremal functions of some forbidden patterns in 0-1 matrices
• Sharper bounds and structural results for minimally nonlinear 0-1 matrices
• Forbidden formations in multidimensional 0-1 matrices
• Tight general bounds for the extremal numbers of 0-1 matrices
• Almost all permutation matrices have bounded saturation functions

This page was built for publication: Linear bounds on matrix extremal functions using visibility hypergraphs

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