کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423551 | 1342419 | 2011 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Degrees of nonlinearity in forbidden 0-1 matrix problems Degrees of nonlinearity in forbidden 0-1 matrix problems](/preview/png/6423551.png)
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.
Journal: Discrete Mathematics - Volume 311, Issue 21, 6 November 2011, Pages 2396-2410