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 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.
展开▼
