Kitaev, Sergey and Mansour, Toufik and Vella, Antoine (2005) Pattern avoidance in matrices. Journal of Integer Sequences, 8.Full text not available in this repository. Request a copy from the Strathclyde author
We generalize the concept of pattern avoidance from words to matrices, and consider specifically binary matrices avoiding the smallest non-trivial patterns. For all binary right angled patterns (0/1 subconfigurations with 3 entries, 2 in the same row and 2 in the same column) and all 2 x 2 binary patterns, we enumerate the m x n binary matrices avoiding the given pattern. For right angled patterns, and the all zeroes 2 x 2 pattern, we employ direct combinatorial considerations to obtain either explicit closed form formulas or generating functions; in the other cases, we use the transfer matrix method to derive an algorithm which gives, for any fixed m, a closed form formula in n. Some of these cases lead naturally to extremal problems of Ramsey type.
|Keywords:||binary matrices, transfer matrix, forbidden submatrices, Ramsey theory, forbidden subsequences, Electronic computers. Computer science, Discrete Mathematics and Combinatorics|
|Subjects:||Science > Mathematics > Electronic computers. Computer science|
|Department:||Faculty of Science > Computer and Information Sciences|
|Depositing user:||Pure Administrator|
|Date Deposited:||15 Oct 2014 04:03|
|Last modified:||10 Mar 2017 05:34|