Degrees of nonlinearity in forbidden 0-1 matrix problems

A 0-1 matrix A is said to avoid a forbidden 0-1 matrix (or pattern) P if no submatrix of A matches P, where a 0 in P matches either 0 or 1 in A. The theory of forbidden matrices subsumes many extremal problems in combinatorics and graph theory such as bounding the length of Davenport-Schinzel sequences and their generalizations, Stanley and Wilf's permutation avoidance problem, and Turán-type subgraph avoidance problems. In addition, forbidden matrix theory has proved to be a powerful tool in discrete geometry and the analysis of both geometric and non-geometric algorithms.Clearly a 0-1 matrix can be interpreted as the incidence matrix of a bipartite graph in which vertices on each side of the partition are ordered. Füredi and Hajnal conjectured that if P corresponds to an acyclic graph then the maximum weight (number of 1s) in an n×n matrix avoiding P is O(nlogn). In the first part of the article we refute of this conjecture. We exhibit n×n matrices with weight Θ(nlognloglogn) that avoid a relatively small acyclic matrix. The matrices are constructed via two complementary composition operations for 0-1 matrices. In the second part of the article we simplify one aspect of Keszegh and Geneson's proof that there are infinitely many minimal nonlinear forbidden 0-1 matrices. In the last part of the article we investigate the relationship between 0-1 matrices and generalized Davenport-Schinzel sequences. We prove that all forbidden subsequences formed by concatenating two permutations have a linear extremal function.

► A refutation of the Füredi-Hajnal conjecture on acyclic 0-1 matrices. ► A new class of forbidden subsequences with a linear extremal function. ► A simplified proof that there are infinitely many minimal nonlinear 0-1 matrices.