Pattern Avoidance in Matrices

Sergey Kitaev,^{1} Toufik Mansour^{2} ^{3} and Antoine Vella^{4} kitaev@ms.uky.edu, toufik@math.haifa.ac.il, avella@math.uwaterloo.ca

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 × 2 binary patterns, we enumerate the m × n binary matrices avoiding the given pattern. For right angled patterns, and the all zeroes 2 × 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.

1 Introduction and Background

The subject of pattern avoidance originated in the context of permutations; the original idea seems to be attributable to Donald Knuth, but the paper by Simion and Schmidt [9] was the one that spawned the large body of work in this area in the last few years. Let π = a_{1}a_{2} ⋯ a_{t}, τ = b_{1}b_{2} ⋯ b_{s} be finite sequences of integers; then a subsequence of π of the same length as τ is said to be an occurrence of τ if its entries occur in the same relative order as in τ. More precisely, given indices i_{1} < i_{2} < ⋯ < i_{s}, the subsequence a_{i_{1}}a_{i_{2}} ⋯ a_{i_{s}} is an occurrence of τ if and only if for all j, k we have a_{i_{j}} < a_{i_{k}} ⇔ b_{j} < b_{k}. Thus for example 451428 is an occurrence of 341325 in 91452174289.

For integers p, q, let us denote by [p, q] the set S = {x ∈ ℤ | p ≤ x ≤ q}. If p = 0, then S is a non-negative interval, and if p = 1, we shorten the notation to [q] and refer to S as a positive interval. Note that, in the above definition of occurrence, if all the a_{i}’s (respectively b_{i}’s) are distinct elements of [t] (respectively [s]), then π (respectively τ) can be thought of as a permutation; otherwise, one can think of words (strings) with integers as the letters.

1Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA

2Research financed by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

3Department of Mathematics, University of Haifa, 31905 Haifa, Israel

4Department of Combinatorics and Optimization, University of Waterloo, Waterloo N2L 3G1, Ontario, Canada

The problems considered in this context are usually enumerative: how many permutations (words) of length n avoid (do not have an occurrence of) a given permutation (word) τ? Apart from the issue of whether the entries are distinct or not, the major difference between the contexts of words or permutations lies in the fact that, in the context of words (strings), while the length of the string is allowed to grow, the entries usually come from a fixed finite alphabet, whereas of course the (distinct) entries of a growing permutation must necessarily come from a growing alphabet. The avoidance problem on words in the sense just described seems to have been first considered by Burstein [3].

In this paper we extend these notions to matrices with integer entries. Although the definitions are, in principle, applicable to matrices with entries from a fixed or growing alphabet, we shall only consider the enumerative problem with a fixed binary alphabet. It turns out that in some specific cases this problem leads to interesting Ramsey-type extremal questions.

Henceforth, m, n will denote positive integers. A matrix A of dimension m × n can be thought of as a function on [m] × [n] which associates to (i, j) the entry a_{i,j} on row i and column j. We say that a subset S ⊆ ℤ^{2} is a shape if both projections {x | ∃y : (x, y) ∈ S} and {y | ∃x : (x, y) ∈ S} are positive intervals. Since we shall be thinking of shapes in relation to subsets of entries of a matrix, we shall denote them pictorially by a collection of tiles in the two-dimensional integer lattice, with the convention (compatible with the usual matrix notation) that the row numbering corresponds to the first coordinate and starts from the top, and the column numbering corresponds to the second coordinate and starts from

the left. Thus for example the symbol stands for the set {(1, 1), (3, 2), (2, 3), (2, 4)}.

We define a pattern to be a surjection from a shape onto a non-negative interval. We shall extend the pictorial notation to represent the function, by placing the image of each

point in the corresponding tile. Thus for example represents the function (pattern)

which associates to the points (1, 1), (3, 2), (2, 3), (2, 4) the images 1, 1, 0, 1 respectively.

Now we define an occurrence of a pattern P in a matrix, by analogy with the case of sequences. Given an m × n-matrix A = (a_{i,j}) with integer entries, we say that a subset T of [m]×[n] is an occurrence of a pattern P : S → [0, s] in A if there exists a bijection ϕ : S → T such that for any two points (i, j), (k, l) ∈ S with (i′, j′) = ϕ((i, j)), (k′, l′) = ϕ((k, l)), we have:

i < k ⇔ i′ < k′ ; j < l ⇔ j′ < l′; and P (i, j) < P (k, l) ⇔ a_{i′, j′} < a_{k′, l′}.

Thus, for example, the set {(1, 2), (2, 5), (2, 7), (3, 4)} is an occurrence of in the matrix

( \begin{matrix}∗ & 3 & ∗ & ∗ & ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ & ∗ & 1 & ∗ & 3 \\ ∗ & ∗ & ∗ & 6 & ∗ & ∗ & ∗ \end{matrix} )

(the ∗ entries are irrelevant, and could be arbitrary integers).

If there are no occurrences of a pattern P in a matrix M, then M is said to avoid P. Given a set Z of patterns, M avoids Z if it avoids every pattern in Z. In this paper we wish to introduce the following generalization of the pattern avoidance problem on words: given the pattern P, or a set of patterns Z, and an integer t, determine the function (m, n) ↦ c_{m,n} which counts the number of different matrices of dimension m × n with entries in [0, t] avoiding P (or Z). In Sections 2 and 3, we tackle the problem in the first case of t = 1, for several small choices of the pattern P. Although P (or Z) may change according to the context, henceforth c_{m,n} will denote the number of m × n matrices avoiding P (or Z).

1.1 The connection to Bipartite Ramsey Problems

Any m × n matrix can be viewed as an edge-colouring of the complete bipartite graph K_{m,n}, whose vertex set is partitioned into two classes A, B with A indexed by the rows and B indexed by the columns, the entry a_{i,j} being the “colour” assigned to the edge corresponding to the i-th row and j-th column.

In this context, the occurrence of a certain pattern in the matrix corresponds to a certain configuration in the coloured graph. This configuration can be more or less interesting from a graph-theoretic viewpoint according to the specific pattern. If the pattern uses only the integer 0, then avoidance of the pattern corresponds to avoidance of a monochromatic copy of this configuration (in any colour); otherwise, the configuration would involve edges of different colours. For certain patterns or sets of patterns, the numbers c_{m,n} turn out to be 0 for large m, n; this gives an unexpected connection to Ramsey Theory in the form of the following question: how large can m, n (or m + n) be so that c_{m,n} > 0? Equivalently, how small can m, n be so that the pattern is “unavoidable” in a matrix of dimension m × n?

Let us consider a few examples. If we take the patterns and , the matrices simultaneously avoiding these two patterns correspond to proper edge colourings of K_{m,n} (an edge colouring is proper if no two edges with the same colour are incident with the same vertex), and it is easy to see that c_{m,n} > 0 ⇔ max{m, n} ≤ t + 1. These edge-colourings can be characterized equally well by requiring that they do not contain a monochromatic copy of P_{3} (for a positive integer k we indicate by P_{k} a path with k vertices and k − 1 edges).

In this paper, we shall only consider the simple case where t = 1; that is, our matrices will have entries in {0, 1}. This does not trivialize the connection to Ramsey Theory. The above considerations imply that, in the language of [8], the bipartite Ramsey numbers b(P_{3}, P_{3}) and b′(P_{3}, P_{3}) are 3 and 4 respectively. Given a pair of bipartite graphs B_{1}, B_{2}, the bipartite Ramsey number b(B_{1}, B_{2}) (respectively b′(B_{1}, B_{2})) is defined as the minimum value of p for which any red/blue edge colouring of K_{p,p} (respectively K_{m,n} for some m + n = p) contains a blue copy of B_{1} or a red copy of B_{2}. We shall write b(B), b′(B) as abbreviations for b(B, B), b′(B, B) respectively.

We may generalize the above example by taking as patterns the two matrices O_{ℓ,k} and O_{k,ℓ}, of dimensions ℓ × k and k × ℓ respectively, with all entries 0. The 0-1 matrices simultaneously avoiding these patterns correspond to edge-colourings which do not contain monochromatic copies of K_{ℓ,k}. In the special case ℓ = k, it is enough to exclude the single pattern O_{ℓ,ℓ}. Harary, Harborth and Mengersen [8] determined the bipartite Ramsey numbers (and the vanishing borders for c_{m,n}) for all pairs of bipartite (not necessarily equal) graphs on at most 5 vertices with no isolated vertices.

The situation may be more complicated when we consider patterns which are not matrices. The pattern , for example, corresponds to a monochromatic copy of P_{4} in which both vertices of degree 2 occur before (with respect to the ordering on A and B) the other vertex in the same class; to eliminate this qualification and simply exclude a monochromatic P_{4}, we need to take all 4 rotations of this pattern together. We may even consider patterns in which the entries are not all equal; for example the matrices , exclude the appearance of an alternating cycle of length 4; the four rotations of exclude the appearance of a copy of P_{4} in which only the middle edge is coloured 1, and taking also the complements (replacing the entry i by 1 − i) gives a set of eight patterns which together exclude alternating paths. In general, for the excluded configuration to have a natural graph-theoretic interpretation, one would want the set of possible occurrences to be closed under at least row and column permutations, preferably under taking the transpose as well, and perhaps even under complementation. Moreover, this on its own may not necessarily imply that the numbers c_{m,n} become 0 for sufficiently large m, n (thus leading to a Ramsey-type problem), as is trivially verified in the case of the alternating cycle.

Thus, apart from the patterns O_{k,ℓ} (which we shall discuss in Section 3.1), in order to obtain natural graph-theoretic Ramsey-type situations in our context one needs to consider simultaneous avoidance of specific, and sometimes large, sets of patterns. On the other hand, as we shall see, a single simple pattern can force the numbers c_{m,n} to vanish for sufficiently large m, n. It is not uncommon to consider Ramsey problems outside the context of graph theory (indeed, Ramsey theory did not arise in the context of graphs at all), so we say that a pattern P is eventually unavoidable if there exists a value q such that every matrix of dimension q × q has an occurrence of P, and for an eventually unavoidable pattern, we define the Ramsey number b(P) to be the smallest possible choice of q. Note that, in general, c_{m′,n′} = 0 ⇒ ∀m ≥ m′, n ≥ n′ we have c_{m,n} = 0. We also define the Ramsey number b′(P) to be the smallest value p for which there exist m, n with m+n = p such that c_{m,n} = 0. Finally, the vanishing border of P, denoted by V (P), is the set of pairs (m, n) such that every matrix of dimension m × n has an occurrence of P, but both (m − 1, n) and (m, n − 1) do not have this property (we adopt the convention that there exist matrices of dimension 0 × n and m × 0). All these definitions are analogous to those given in [8] for pairs of bipartite graphs.

The focus of this paper is intended to be enumerative, rather than extremal: to determine the numbers c_{m,n}, rather than just their vanishing border. We shall consider almost exclusively avoidance of a single pattern P, for certain small examples of P, and we shall not aim for results of Ramsey type. However, we shall state a few extremal results that we obtain as by-products, and attempt to raise relevant questions which are interesting from the point of view of Ramsey Theory.

1.2 Equivalent patterns and some specific shapes

Recall that shapes are formally subsets of ℤ^{2}, and all their elements have both coordinates positive. Let S be any shape; reflecting S about any one of the four axes of symmetry of ℤ^{2}, (the vertical, horizontal and diagonal lines through the origin) yields a set S′ which may not be a shape; however, there always exists a unique translation S′′ of S′ that is itself a shape. We shall always assume that these reflections are accompanied by this translation, so that they associate shapes to shapes, patterns to patterns and matrices to matrices. Thus, for example, is obtained by reflecting about the horizontal axis. For a fixed value of t, another useful operation on patterns and matrices is that of complementation: replacing each entry i by z −i, where z = s in the case of a pattern P : S → [0, s], and z = t in the case of matrices (formally, this amounts to post-composing the pattern/matrix with the function i ↦ z − i). Thus for example, the pattern is its own complement, is the complement of , and for t = 1, the matrix ( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} ) is the complement of ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ).

The above operations of reflection and complementation are all involutions on the sets of patterns and matrices which preserve occurrences, in the sense that if χ is one of the above operations, P is a pattern and M is a matrix, then P occurs in M if and only if χ(P) occurs in χ(M)^{5}. Clearly, the same is true if χ is any composition of these operations. Note that reflecting a matrix about the line y = x corresponds to taking its transpose^{6}. For this reason, we also refer to the reflection of a pattern P about this line as the transpose of P. As in classical permutation avoidance, these operations are useful in reducing the enumeration of pattern-avoiding matrices to a smaller number of cases (patterns).

The analysis of avoidance of a single pattern of dimension 1 × n or m × 1 can easily be reduced to that of avoidance of the pattern in each row (column) of the matrix independently. This problem has been considered by Burstein and Mansour [4, 5, 6]. In this paper we do not attempt to deal with such patterns.

Instead, we consider the following two basic configurations: right angled and square shapes, and all possible binary patterns on these shapes (note that given any shape S and an integer t, there is only a finite number of patterns P : S → [0, s] with s ≤ t). The right angled shapes are , , and ; a pattern is right angled if its domain is a right angled shape. The square shape is , and the square patterns are the 2 × 2 matrices.

If t = 1, each right angled shape can be numbered in 8 ways, which reduce to 7 patterns, for a total of 28 possible right angled patterns. The operations mentioned above reduce these to three equivalence classes, which we represent by , and . In Section 2 we shall see that these three cases in fact reduce to two: the numbers c_{m,n} are the same for the patterns and . The 16 square binary matrices reduce to 15 square patterns, but the above operations allow us to restrict our attention to the following four patterns: , ,

, and .

2 Right angled patterns

2.1 Avoidance of the pattern

We observe that since the pattern is its own transpose, a matrix avoids if and only if its transpose does. So it is enough to consider matrices of size m × n, where m ≥ 2 and n ≥ m.

In the proof of Proposition 1 and throughout the paper, we use phrases like “this column does not affect the rest of the matrix” to mean “the entries in this column can not occur as part of a forbidden pattern in the matrix”; this allows us to obtain recurrence relations.

5Note that, if χ is the operation of complementation, χ(M) may actually depend on whether we are considering M as a pattern or a matrix avoiding a given pattern.

6Recall the row-numbering increases downwards.

Proposition 1. In the case of the pattern , we have that c_{2,n} = 2^{n+2} − 4 for n ≥ 1; c_{3,3} = 16; c_{3,n} = 0 for n ≥ 4; and c_{m,n} = 0 for n ≥ m ≥ 4.

Proof. Assuming that n ≥ m, let A be an m × n matrix that avoids the pattern .

The case m = 2. If the first column of A is \binom{1}{0} or \binom{0}{1}, then obviously this column does not affect the rest of the matrix, and we have 2c_{2,n−1} possibilities to choose A in this case.

If the first column of A is \binom{0}{0} (respectively, \binom{1}{1}), then from the second entry onwards the first row of A can consist only of 1’s (respectively, 0’s) since otherwise we have an occurrence of the pattern with the first column of A as the first column of the occurrence. All the entries in the second row, except possibly the last one, must be 0 (respectively, 1), for otherwise we would have a literal occurrence of the numbered shape (respectively, )— which is an occurrence of the pattern —with the first row of the occurrence contained in the first row of the matrix. Thus, in this case we can choose the first row in 2 ways and then choose the rightmost bottom entry in 2 ways. Summarizing our considerations, we get the following recurrence relation

c_{2,n} = 2c_{2,n−1} + 4,

with c_{2,1} = 4. This gives that c_{2,n} = 2^{n+2} − 4.

The case m = 3. Obviously it suffices to consider the case n = 4.

Suppose, by way of contradiction, that the matrix A avoids . Without loss of generality A_{1,1} = 0. If the remaining three elements of the first row are 1, then all the elements in the lower right 2 × 3 submatrix, except possibly A_{3,4}, are 0, and a contradiction results. So some other entry of the first row is also 0. Then it immediately follows that A_{2,1} = A_{3,1} = 1 and hence also that A_{2,2} = A_{2,3} = A_{2,4} = 0 and A_{3,2} = A_{3,3} = 1. This yields the partially filled matrix

( \begin{matrix}0 & ∗ & ∗ & ∗ \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & ∗ \end{matrix} )

with at least two 0’s in the first row. One can see that we can not have three 0’s in the first row, and thus we have two 1’s in the first row which also creates the forbidden pattern.

The case m = 4. Follows from the case m = 3 and n ≥ 4.

2 3 4 5 ⋯
2 4 12 28 60 ⋯
3 12 16 0
4 28 0
5 60
⋮ ⋮

The numbers c_{m,n} for the pattern

Corollary 2. The pattern is eventually unavoidable. Its Ramsey numbers satisfy b ( ) = 4, b′ ( ) = 7. The vanishing border is given by V ( ) = {(3, 4), (4, 3)}.

2.2 Avoidance of the pattern

Proposition 3. In the case of the pattern , we have that

∑_{m,n≥0} c_{m,n}x^{m}y^{n} = ∑_{m≥0} \frac{\frac{x^{n}y}{1−(n+1)y}}{∏_{j=0}^{m} (x + \frac{(1−x)y}{1−jy})}.

Proof. Let A be an m × n matrix avoiding the pattern . Clearly, an empty matrix avoids π, so c_{m,0} = c_{0,n} = 1. Suppose that A is a matrix of size m × n with m, n ≥ 1.

If the top row of A contains only zeros, then it does not affect the rest of the matrix and can be removed to obtain a -avoiding matrix of m − 1 rows and n columns. Now suppose the top row of A contains a 1. Suppose that in the top row there are i zeros to left of the rightmost 1. Since A avoids , the i columns containing those top zeros must be zero columns. Thus, these columns can not be involved in an occurrence of , so they may be removed. The resulting top row has all 1s to the left of all 0s, so this top row can not be involved in an occurrence of , and hence, may be removed as well. Each choice of i + 1 positions (those of the rightmost 1 in the top row and i zeros to its left) yields, after the two removals, an (m − 1) × (n − i) matrix avoiding . Thus,

c_{m,n} = c_{m−1,n} + ∑_{i=0}^{n−1} \binom{n}{i + 1}c_{m−1,n−i}, m, n ≥ 1.

Straightforward technical manipulations, which are omitted, the ordinary generating function a(x, y) = ∑_{n,m≥0} c_{m,n}x^{m}y^{n} satisfies the following recurrence

a(x, y) = \frac{y}{(1 − y)(x + (1 − x)y)} + \frac{x}{x + (1 − x)y} a (x, \frac{y}{1 − y} ) .

The result follows by repeatedly applying this recursion and taking the limit.

2.3 Avoidance of the pattern

One can apply the same considerations made in Subsection 2. The only difference between these cases is that instead of 0’s below each 0 in the first row, we have 1’s. This gives a recursive bijection between the matrices avoiding the pattern and those avoiding the pattern . Thus we obtain the following analogous result.

Proposition 4. In the case of the pattern , we have that

∑_{m,n≥0} c_{m,n}x^{m}y^{n} = ∑_{m≥0} \frac{\frac{x^{n}y}{1−(n+1)y}}{∏_{j=0}^{m} (x + \frac{(1−x)y}{1−jy})}.

3 Square patterns

3.1 Avoidance of the pattern

We make the same observation made in Subsection 2.1, that is, a matrix avoids the pattern

if and only if its transpose avoids the transpose of , which is itself. So it is enough to consider matrices of size m × n with m ≥ 2 and n ≥ m. Moreover, the pattern has the following properties that are easy to see

1) a matrix avoids if and only if its complement does;

2) permuting columns and rows of a matrix M produces a matrix that avoids the pattern if and only if M does.

Proposition 5. In the case of the pattern , we have that c_{2,n} = (n^{2} + 3n + 4)2^{n−2} for n ≥ 0; c_{3,3} = 168; c_{3,4} = 408; c_{4,4} = 3240; c_{3,n} = c_{4,n} = 720 for n = 5, 6; c_{3,n} = c_{4,n} = 0 for n > 6; and c_{m,n} = 0 for n ≥ m ≥ 5.

Proof. Let A be an m × n matrix, that avoids the pattern .

The case m = 2. We consider only the case A_{1,1} = 0, since the case A_{1,1} = 1 gives the same number of matrices avoiding , by property 1 above. If A_{2,1} = 1, then the first column of A does not affect the rest of the matrix, and therefore we have c_{2,n−1} possibilities to choose A in this case. If A_{2,1} = 0 then no column of A other than the first can be \binom{0}{0}, since this leads to an occurrence of in A. On the other hand, A obviously can not contain two columns which are both copies of \binom{1}{1}. So, either A does not contain \binom{1}{1} or else it contains precisely one such column. In the first case we have 2^{n−1} possibilities for A, since any column except the first one is either \binom{1}{0} or \binom{0}{1}. In the second case, we can choose the position in which we have \binom{1}{1} in (n − 1) ways, and then choose all other columns in 2^{n−2} ways. Thus we get the recurrence

c_{2,n} = 2 · (c_{2,n−1} + (n + 1)2^{n−2}),

which gives the desired result.

The case m = 3. To deal with this case we make use of the following four facts. Fact 1. There are no columns in A that are equal to each other. This is easy to see, since otherwise we have an occurrence of the pattern .

Fact 2. If both of the columns ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) and ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) appear in A, then A can not have more than two columns. Indeed, using the fact that permuting the columns of A does not affect avoidance of the pattern , we can assume that the first two columns of A are ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) and

( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ). Adding one more column will introduce an occurrence of the pattern , since it will contain either two 1’s or two 0’s. Fact 3. If A contains either the column ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or the column ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ), then the other columns can only be chosen from a set consisting of three columns, without repetitions. In the first case these columns are ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ), ( \begin{matrix}1 \\ 0 \\ 1 \end{matrix} ), and ( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ), whereas in the second case they are ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ), ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ), and ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ). This is easy to see, since otherwise we obviously have an occurrence of

the pattern .

Fact 4. If A does not contain ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ), then the columns of A can be chosen from among all the other six binary columns of length 3, without repetitions. This follows from the fact that once these two columns are excluded, any column must contain the same letter in two positions, and once these two entries are given, the third is uniquely determined; thus any two columns will give an occurrence of if and only if they are equal.

As a corollary of Facts 1–4 we have the following

c_{3,3} = 2 · 3 · 3 · 2 + \frac{6!}{3!} = 156; c_{3,4} = 2 · 4! + \frac{6!}{2!} = 408;

c_{3,5} = c_{3,6} = 6! = 720; c_{3,n} = 0 if n > 6;

where, for instance, to obtain c_{3,3} we first count the number of those matrices that have either ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) as a column (of which, according to Fact 3, there are precisely 2 · 3 · 3 · 2), and

then we add the number of matrices that do not contain ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ) (of which, according to Fact 4, there are as many as there are permutations of three columns chosen from six columns).

The case m = 4. Suppose first that n ≥ 5. If a column of A has either at least three 0’s or at least three 1’s, then we can consider the three rows that form a matrix having the column ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) or ( \begin{matrix}1 \\ 1 \\ 1 \end{matrix} ). The length of such a matrix, according to Fact 3, does not exceed 4, and the columns of A in this case are those that have exactly two 0’s and two 1’s. It is easy to see that any combination of such columns gives no occurrences of the pattern , and there are six such columns. Thus, c_{4,5} = c_{4,6} = 6! = 720.

Now let n = 4. If any column of A has exactly two 0’s and two 1’s, the number of ways to choose A in this case is \frac{6!}{2!} = 360. If some column has only 0’s or only 1’s, say only 0’s, then the number of columns does not exceed 2, since the other columns can not have more than one 0, and two such columns must have an occurrence of the pattern . So, we need only consider the case when there is a column in A having three 0’s or three 1’s. Suppose there is a column with three 0’s. In this case we can assume, permuting rows or columns if necessary, that A_{1,1} = A_{2,1} = A_{3,1} = 0 and A_{4,1} = 1. If we consider the submatrix that is formed by the first three rows and the four columns, then according to the considerations of the case m = 3, this submatrix is a permutation of the columns ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ), ( \begin{matrix}1 \\ 0 \\ 1 \end{matrix} ), and ( \begin{matrix}1 \\ 1 \\ 0 \end{matrix} ). Obviously, the entries A_{4,2}A_{4,3}A_{4,4} form a word that has at most one 1. Thus, there are 4 ways to choose this word, and then we can permute columns and rows in 4! · 4! ways to get different 4 × 4 matrices avoiding . So, in this case we have 4 · 24 · 24 = 2304 different matrices. Finally, we need to count the number of matrices that have a column with three 1’s and have no columns with three 0’s. We use the same considerations as in the case of three 0’s, but now we observe that the entries A_{4,2}A_{4,3}A_{4,4} can only form the word 111 (otherwise we have a column with three 0’s or an occurrence of the pattern ). Thus this case gives us 4! · 4! = 576 different matrices. So the total the number of 4 × 4 matrices avoiding the pattern is given by 360 + 2304 + 576 = 3240.

The case m ≥ 5. The first row of A has either at least three 0’s or at least three 1’s. In either case, if we consider the three rows of A that begin with the same letter, we have that, according to Fact 3, the length of these rows does not exceed 4, since otherwise they will contain the pattern . Thus, A must have at most four columns in order to avoid .

2  3  4  5  6  7 ⋯
2 14 44 128 352 928 2368 ⋯
3 44 168 408 720 720 0
4 128 408 3240 720 720
5 352 720 720 0
6 928 720 720
7 2368 0
⋮  ⋮

The numbers c_{m,n} for the pattern

Remark 6. From the above proposition we can deduce some known (and easy) facts about the bipartite Ramsey numbers of K_{2,2}. First of all, the pattern is eventually unavoidable; moreover, the vanishing border V ( ) is {(3, 7), (5, 5), (7, 3)} (equivalently, the “bipartite Ramsey set β(K_{2,2}, K_{2,2})” is {(3, 7), (5, 5)}, in the language of [8]), and b ( ) = b(K_{2,2}) = 5 and b′ ( ) = b′(K_{2,2}) = 10. All these results are contained explicitly or implicitly in [8], and any credit for the computation of b(K_{2,2}) should probably be attributed to Beineke and Schwenk [2].

Proposition 7. Let c_{m,n} denote the number of matrices that avoid the pattern O_{ℓ,k}. If we set \overline{m} = 2ℓ − 1, n̄ = 2(k − 1)\binom{2ℓ−1}{ℓ} + 1, we have that

(1) c_{m,n} > 0 for m < \overline{m};

(2) c_{\overline{m},n} = 0 ⇔ n ≥ n̄;

(3) c_{m,n} = 0 for m > \overline{m}, n ≥ n̄.

In particular, O_{ℓ,k} is eventually unavoidable and (\overline{m}, n̄) belongs to its vanishing border.

Proof. Suppose A = (a_{i,j}) is a matrix of dimensions \overline{m} × n̄. By the Dirichlet Principle, each column of A has either at least ℓ 1’s or at least ℓ 0’s (but not both). For p = 0, 1, let C_{p} be the set of indices j such that column j has a majority of p’s. Again by the Dirichlet principle, there is some q ∈ \{0, 1\} such that |C_{q}| ≥ ⌈\frac{n̄}{2}⌉ = (k − 1)\binom{2ℓ−1}{ℓ} + 1. Then for all j ∈ C_{q}, there exists some subset S_{j} ⊆ [\overline{m}] with |S_{j}| = l such that for all i ∈ S_{j}, we have a_{i,j} = q. Since the total number of subsets of [\overline{m}] with l elements is \binom{2ℓ−1}{l}, again by the Dirichlet principle our choices of S_{i} must agree for at least k columns, that is, S_{i} = S ∀ i ∈ T for some S ⊆ [\overline{m}] and T ⊆ C with |T | = k. Then S × T is an occurrence of O_{ℓ,k}. Thus c_{\overline{m},n̄} = 0. This proves (3) and the backward implication in (2).

On the other hand, for any m ≤ 2ℓ − 2 and any n, a matrix of dimensions (\overline{m} − 1) × n̄ avoiding O_{ℓ,k} can easily be constructed by allowing at most ℓ − 1 0’s and ℓ − 1 1’s in each column. This proves (1). Moreover, the matrix of dimensions \overline{m} × (n̄ − 1) whose columns all have precisely ℓ 0’s or ℓ 1’s, and such that for all S ⊆ [\overline{m}] with |S| = ℓ there are precisely k columns with 1’s precisely on rows indexed by S, and precisely k (other) columns with 0’s precisely on rows indexed by S, for a total of 2(k − 1)\binom{2ℓ−1}{ℓ} columns, avoids the pattern O_{ℓ,k}. This concludes the proof of (2). Thus both c_{\overline{m}−1,n̄} and c_{\overline{m},n̄−1} are positive and (\overline{m}, n̄) ∈ V (O_{ℓ,k}).

Corollary 8. Let ℓ, k be positive integers. We have that b(O_{ℓ,k}) = b(O_{k,ℓ}) and b′(O_{ℓ,k}) = b′(O_{k,ℓ}). Assuming without loss of generality that ℓ ≤ k, the following upper bounds hold

b(K_{ℓ,k}) ≤ b(O_{ℓ,k}) ≤ 2(k − 1)\binom{2l − 1}{l} + 1  (1)

b′(K_{ℓ,k}) ≤ b′(O_{ℓ,k}) ≤ 2(k − 1)\binom{2l − 1}{l} + 2ℓ.  (2)

Proof. Note that a matrix avoids O_{ℓ,k} if and only if its transpose avoids O_{k,ℓ}. From this it follows that V (O_{ℓ,k}) = {(b, a) | (a, b) ∈ V (O_{k,ℓ})}. As observed in [8], for any bipartite graph G, b(G) = min{max{a, b} | (a, b) ∈ V (G)} and b′(G) = min{a + b | (a, b) ∈ V (G)}, and the analogous statements hold for any pattern P instead of a graph G. In particular, since the sum and the maximum of two variables are commutative, these minima coinicide when taken over the two vanishing borders. Moreover, since (\overline{m}, \overline{n}) ∈ V (O_{ℓ,k}) (with \overline{m}, \overline{n} defined as in Proposition 7), \overline{m} + \overline{n} and max\{\overline{m}, \overline{n}\} are upper bounds for b′(O_{ℓ,k}) and b(O_{ℓ,k}) respectively. The former simplifies to the rightmost expression in (2), and the latter, with the assumption ℓ ≤ k, to the rightmost expression in (1). The inequalities b(K_{ℓ,k}) ≤ b(O_{ℓ,k}) and b′(K_{ℓ,k}) ≤ b′(O_{ℓ,k}) follow from the trivial observation that if the edges of K_{m,n} can be coloured to avoid a monochromatic copy of K_{ℓ,k}, the corresponding binary m × n matrix avoids O_{ℓ,k} (as well as O_{k,ℓ}).

Remark 9. We have no reason to believe that the above bounds are good, and we expect that they can be improved. Good bounds are known for b(K_{ℓ,k}); see for example [12]. The Ramsey number b′(K_{ℓ,k}) seems to have received less attention, but an obvious upper bound is given by 2b(K_{ℓ,k}). The question arises as to how big the gap between b(K_{ℓ,k}) and b(O_{ℓ,k}) is (and analogously for b′). This issue runs a parallel with the conjecture of Simonovits [10] that ex^{∗}(n, L) = O(ex(n, L)), where for a bipartite graph L, ex(n, L) denotes the smallest number of edges of K_{m,n} needed to ensure that the induced subgraph contains a copy of L, while ex^{∗}(n, L) stands for the minimum number of 1’s in an m×n matrix that ensures the existence of a “submatrix” whose entries all are 1, and equivalent to the bipartite adjacency matrix B of L. The issue of equivalence is irrelevant in our context because our bipartite graphs are complete. The parallel lies in the distinction between the “ordered” and “unordered” versions: whether we care that the ℓ prescribed vertices in the copy of K_{ℓ,k} are among the prescribed m of K_{m,n} or not. Note however that there is a crucial difference between the two problems: we are here talking of excluding only (ℓ × k)-minors (for complete bipartite L) whose entries are all 1, but not those whose entries are all 0’s, which also need to be excluded to avoid the pattern O_{ℓ,k} (or a monochromatic copy of K_{ℓ,k}).

Also note that, if f(x) = 2x − 1 and g(x, y) = 2(y − 1)\binom{2x−1}{x}, both (f(ℓ), g(ℓ, k)) and (g(k, l), f(k)) belong to the vanishing border of O_{ℓ,k}, and both points can be used to derive upper bounds; in Corollary 8 we have given the stronger one, with the assumption that ℓ ≤ k.

3.2 Avoidance of the patterns , , and

In this section we see how the transfer matrix method can be used to obtain, for fixed m, an explicit formula for the number of binary matrices of dimensions m × n avoiding a pattern from the set S = { , , }.

For fixed m ≥ 1 and p ∈ S, we denote by B^{m,∗} (B^{m,n}) the set of all binary matrices with m rows (respectively, m rows and n columns), and define an equivalence relation ∼_{p} on B^{m,∗} by A ∼_{p} B if and only if for all vectors u ∈ B^{m,1} we have

A|u avoids p ⟺ B|u avoids p,

where the notation A|u stands for the matrix obtained by concatenating the vector u to the

matrix A. For example, if p is , m = 3, A = ( \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix} ) and B = ( \begin{matrix}1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix} ), then

A ∼_{p} B, since the entries in the third column in A are never involved in an occurrence of p. Let E_{p} be the set of equivalence classes of ∼_{p}. We denote the equivalence class of a binary matrix A by \overline{A}. For example, the equivalence classes of ∼_{p} for p = and m = 2 are

\overline{ϵ}, \overline{( \begin{matrix}0 \\ 0 \end{matrix} )}, and \overline{( \begin{matrix}0 & 0 \\ 0 & 1 \end{matrix} )}

where ϵ stands for the empty matrix.

Definition 10. Given a positive integer m and a pattern p we define a finite automaton^{7}, A_{p} = (E_{p}, δ, \overline{ϵ}, E_{p} \ \{\overline{p}\}), by the following

• the set of states, E_{p}, consists of the equivalence-classes of ∼_{p};

• δ : E_{p} × B^{m,1} → E_{p} is the transition function defined by δ(\overline{A}, u) = \overline{A|u};

• \overline{ϵ} is the initial state;

• and all states but \overline{p} are final states.

We wish to enumerate the number of binary matrices of size m × n avoiding the pattern p. We shall identify A_{p} with the directed graph^{8} with vertex set E_{p}\\{\overline{p}\} and with a (labelled) edge ⟶^{u} from \overline{A} to \overline{B} whenever A|u ∼_{p} B. Note that, whenever we have an edge from \overline{A} to \overline{B}, the outdegree of \overline{B}, that is, the number of binary vectors u ∈ B^{m,1} such that B|u ≁_{p} B but B|u still avoids p, is strictly less than the outdegree of \overline{A}. Hence, we may choose binary matrices {A^{(i)}}_{i=1}^{e} as representatives of the vertices (equivalence classes), indexed in such a way that if i < j there is no edge from \overline{A^{(j)}} to \overline{A^{(i)}}; in particular there are no directed cycles in the graph, and \overline{A^{(1)}} = \overline{ϵ}. Let e denote the cardinality of E_{p}. The transition matrix, T_{p}, of A_{p} is the e × e -matrix,

7For a definition of a finite automaton, see [1] and references therein.

8Here we are allowing loops and multiple edges, and following the terminology of [7].

[T_{p}]_{ij} = |\{u ∈ B^{m,1} : δ(A^{(i)}, u) = \overline{A^{(j)}}\}|.

Thus [T_{p}]_{ij} counts the number of edges from \overline{A^{i}} to \overline{A^{j}}, and with the above choice of indices T_{p} is upper triangular.

Example 1. Let p = and fix m = 3; then it is easy to see that a possible choice of representatives is

A^{(1)} = ϵ, A^{(2)} = ( \begin{matrix}1 \\ 0 \\ 0 \end{matrix} ), A^{(3)} = ( \begin{matrix}0 \\ 1 \\ 0 \end{matrix} ), A^{(4)} = ( \begin{matrix}0 \\ 0 \\ 1 \end{matrix} ),

A^{(5)} = ( \begin{matrix}0 & 1 \\ 1 & 0 \\ 0 & 0 \end{matrix} ) and A^{(6)} = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ).

The transition matrix T_{p} is

(\begin{matrix}4 & 1 & 1 & 1 & 0 & 1 \\ 0 & 4 & 0 & 0 & 1 & 1 \\ 0 & 0 & 4 & 0 & 1 & 1 \\ 0 & 0 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 0 & 4 & 1 \\ 0 & 0 & 0 & 0 & 0 & 4 \end{matrix}) .

Given a matrix A let (A; i, j) be the matrix with row i and column j deleted. Using the transfer matrix method (see [11, Theorem 4.7.2]) together with the automaton A_{p} we obtain our main result in this section.

Theorem 11. In the case that the pattern p is a matrix of size 2 × 2, for any fixed positive integer m we have that

∑_{n≥0} c_{m,n}x^{n} = \frac{∑_{j=1}^{e} (−1)^{j+1} det(I − xT_{p}, j, 1)}{∏_{i=1}^{e}(1 − λ_{i}x)} = \frac{det B(x)}{∏_{i=1}^{e}(1 − λ_{i}x)},

where

• T_{p} is the transition matrix, of dimensions e × e, of the finite automaton A_{p}, as defined in Definition 10, and therefore depends on p and m;

• B(x) is the matrix obtained by replacing the first column in I − xT_{p} with a column of all ones;

• and λ_{i} is the number of loops at state A^{(i)}.

Given a pattern p, let us denote by B^{m,n}(p) the set of matrices of dimensions m × n avoiding the pattern p. Theorem 11 provides a finite algorithm for finding the generating function for the sequence {|B^{m,n}(p)|}_{n≥0} for any fixed m ≥ 1 and any pattern p which is a matrix of size 2 × 2. The algorithm has been implemented in C and Maple.

Corollary 12. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−1},

(ii) |B^{3,n}( )| = \frac{1}{3}(2 + n)(96 + 31n + n^{2})4^{n−3},

(iii) |B^{4,n}( )| = \frac{1}{36}(2812500 + 3963450n + 1862971n^{2} + 339300n^{3} + 21265n^{4} + 510n^{5} + 4n^{6})5^{n−7},

(iv) B^{5,n}( )| = \frac{1}{105}(1371372871680+2829503247984n+2174816371140n^{2}+785515085820n^{3}+ 139879643143n^{4}+12307090320n^{5}+579047595n^{6}+15070860n^{7}+218757n^{8}+1656n^{9}+5n^{10})6^{n−13}.

Corollary 13. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−1},

(ii) |B^{3,n}( )| = \frac{1}{3}(2 + n)(96 + 31n + n^{2})4^{n−3},

(iii) |B^{4,n}( )| = \frac{1}{36}(2812500 + 3963450n + 1862971n^{2} + 339300n^{3} + 21265n^{4} + 510n^{5} + 4n^{6})5^{n−7},

(iv) |B^{5,n}( )| = \frac{1}{350}(4571242905600+9431397663120n+7249916118636n^{2}+2618093085240n^{3}+ 466294991825n^{4} + 41039857215n^{5} + 1926425298n^{6} + 50381010n^{7} + 729825n^{8} + 5415n^{9} + 16n^{10})6^{n−13}.

Corollary 14. For all n ≥ 0, (i) |B^{2,n}( )| = (3 + n)3^{n−1},

(ii) |B^{3,n}( )| = (16 + 13n + 3n^{2})4^{n−2},

(iii) |B^{4,n}( )| = (25 + 34n + 18n^{2} + 3n^{3})5^{n−2},

(iv) |B^{5,n}( )| = (216 + 418n + 361n^{2} + 140n^{3} + 17n^{4})6^{n−3}.

Note that no two patterns in S give the same formulas, although the distinction between the patterns and does not become apparent before m = 5. We also remark that our approach can be generalized to matrices with t > 1 letters and simultaneously avoiding different sets of patterns. For example, the following result is true.

Corollary 15. We have that (i) the number of matrices of size 3 × n on 3 letters avoiding the pattern is given by

\begin{matrix}\frac{1}{2}(1582178 − 269829n + 6241n^{2})13^{n−2} \\ −(673920 − 61130n − 4427n^{2} − 106n^{3} − n^{4})12^{n−2}; \end{matrix}

(ii) the number of binary matrices of size 2 × n simultaneously avoiding the patterns and is given by

2 · 3^{n} − 2^{n}.

Acknowledgements. The authors are grateful to the referee for the careful reading of the manuscript and shortening the proof of Proposition 3. The first version of this paper was written during the three authors stay at Chalmers University of Technology. The authors want to express their gratitude to Chalmers for the support.

References

[1] A. V. Aho, R. Sethi, J.D. Ullman. Compilers: principles, techniques and tools, Addison-Wesley, Reading, Mass., 1986.

[2] L.W. Beineke, A.J. Schwenk. On a bipartite form of the Ramsey problem, Proc. Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) 17–22. Congressus Numerantium XV, Utilitas Math., Winnipeg, Man., 1976.

[3] A. Burstein. Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998.

[4] A. Burstein, T. Mansour. Words restricted by patterns with at most 2 distinct letters. Permutation patterns (Otago, 2003). Electron. J. Combin. 9 (2002/2003), no. 2, Research paper 3, 14pp (electronic).

[5] A. Burstein, T. Mansour. Counting occurrences of some subword patterns. Discrete Math. Theor. Comput. Sci. 6 (2003), no. 1, 1–11 (electronic).

[6] A. Burstein, T. Mansour. Words restricted by 3-letter generalized multipermutation patterns. Ann. Combin. 7 (2003), no. 1, 1–14.

[7] R. Diestel. Graph Theory, Springer-Verlag, New York, 1997.

[8] F. Harary, H. Harborth, I. Mengersen. Generalized Ramsey Theory for Graphs XII: Bipartite Ramsey Sets, Glasgow Math. J. 22 (1981), 31–41.

[9] R. Simion, F.W. Schmidt. Restricted Permutations, Europ. J. Combin. 6 (1985), 383–406.

[10] M. Simonovits. Paul Erdős’ Influence on Extremal Graph Theory, The Mathematics of Paul Erdős II, (Graham, Nešetřil eds.) 148–192. Algorithms Combin. 14, Springer, Berlin, 1997.

[11] R. Stanley. Enumerative Combinatorics, Volume 1, Cambridge University Press, Cambridge, 1997.

[12] A. Thomason. An upper bound for some Ramsey numbers, J. Graph Theory 12 (1988), no. 4, 509–517.

2000 Mathematics Subject Classification: Primary 05A05, 05A15; Secondary 05D10, 05C50. Keywords: Binary matrices, Ramsey Theory, Forbidden subsequences, Forbidden submatrices, Transfer matrix.

(Concerned with sequence \underline{A027649,A006234,A007466}.)