Pattern avoidance in matrices

Sergey Kitaev, Toufik Mansour, Antoine Vella

Research output: Contribution to journalArticle

7 Citations (Scopus)

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.
Original languageEnglish
Article number05.2.2
Number of pages16
JournalJournal of Integer Sequences
Volume8
Publication statusPublished - 2005

Keywords

  • binary matrices
  • transfer matrix
  • forbidden submatrices
  • Ramsey theory
  • forbidden subsequences

Cite this