Linear bounds on matrix extremal functions using visibility hypergraphs

The 0–1 matrix AA contains a 0–1 matrix MM if some submatrix of AA can be transformed into MM by changing some ones to zeros. If AA does not contain MM, then AA avoids MM. Let ex(n,M)ex(n,M) be the maximum number of ones in an n×nn×n 0–1 matrix that avoids MM, and let exk(m,M)exk(m,M) be the maximum number of columns in a 0–1 matrix with mm rows that avoids MM and has at least kk ones in every column. A method for bounding ex(n,M)ex(n,M) by using bounds on the maximum number of edges in bar visibility graphs was introduced in Fulek (2009). By using a similar method with bar visibility hypergraphs, we obtain linear bounds on the extremal functions of other forbidden 0–1 matrices.