Degrees of nonlinearity in forbidden 0-1 matrix problems

作者：Pettie Seth^*

来源：Discrete Mathematics, 2011, 311(21): 2396-2410.

DOI：10.1016/j.disc.2011.06.020

• Forbidden matrix
• Turan number
• Davenport-Schinzel sequence

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 extrema] problems in combinatorics and graph theory such as bounding the length of Davenport-Schinzel sequences and their generalizations. Stanley and Wilt's permutation avoidance problem, and Turan-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. Furedi and Hajnal conjectured that if P corresponds to an acyclic graph then the maximum weight (number of 1s) in an n x n matrix avoiding P is 0(n log n). In the first part of the article we refute of this conjecture. We exhibit n x n matrices with weight Theta(n log n log log n) 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.

• 出版日期2011-11-6