Pattern avoidance in matrices

Tools

Kitaev, Sergey and Mansour, Toufik and Vella, Antoine (2005) Pattern avoidance in matrices. Journal of Integer Sequences, 8. 05.2.2.

Full text not available in this repository.Request a copy

Abstract

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.

ORCID iDs

Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Mansour, Toufik and Vella, Antoine;
CORE (COnnecting REpositories)