Page 50 - Textos de Matemática Vol. 39

40 RAFAEL CANTO´ AND CHARLES R. JOHNSON
Lemma 1.1. If t(m,n,r)<r, then t(m+1,n+1,r+1)<r+1.
Proof. Let P = (pij ) be an m-by-n pattern such that mr(P ) = r and P has no r-triangles. We wish to construct an (m + 1)-by-(n + 1) pattern Q = (qij ) such that mr(Q) = r + 1 and Q contains no (r + 1)-triangles.
Let Q = [∗]⊕P, which is the (m+1)-by-(n+1) pattern with the first row and column have only one nonzero entry in the position q11 and qij = pi−1,j−1, for 2 ≤ i ≤ m+1, 2 ≤ j ≤ n+1. By [2, Proposition 2.4] we have mr(Q) = r+1. We need only show that MT(Q) = MT(P ) + 1. It is clear that it is not less. Consider a maximum triangle in Q; it must use the first row or column of Q (else no increase in triangle size). If it does not use both, the triangle would have a 0 line (impossible). When it uses both, the triangle is of the form [∗]⊕T, in which T is a triangle of P, completing the proof.
Lemma 1.2. If t(m,n,r)<r, then t(m+1,n,r)<r and t(m,n+1,r)<r.
Proof. Let P be an m-by-n pattern such that mr(P) = r and P has no r-triangles. We want to exhibit the existence of an (m + 1)-by-n pattern Q such that mr(Q) = r and Q has no r-triangles. (The case m-by-(n + 1) is similar).
Construct Q as follows. Duplicate the first row of P = (pij ) that is,
⎡⎢ p 1 1 p 1 2 · · · p 1 n ⎤⎥
⎢ p11 p12 ··· p1n ⎥ Q=⎢p21 p22 ···p2n⎥.
⎢⎣ . . . ⎥⎦ pm1 pm2 ··· pmn
It is clear [2, Proposition 2.2] that mr(Q) = mr(P ) = r. We want to show that k = MT(Q) = MT(P) < r. Let i1,...,ik; j1,...,jk be the rows and columns of a (maximum) k-triangle Qk of Q. If i1 ̸= 1, this k-triangle lies in P , so that, k = MT(P) and the proof would be complete. Suppose i1 = 1 holds. Because a triangle has no repeated rows and no repeated columns, if i1 = 1, i2 ̸= 2. However, if i1 = 1, replacement of i1 in Qk by i1 = 2, leaves the same pattern. Thus, even if i1 = 1, there is a triangle in P realizing MT(Q), so that the claim of the lemma follows.
Corollary 1.3. If t(n,n,r)<r, then t(n+1,n+1,r)<r.
It is not difficult to see that t(m,n,r) = r for r = 0,1, or 2, but this will
be implied by the following rather more subtle fact.
Lemma 1.4. For any m,n ≥ 3, t(m,n,3) = 3.
Proof. Suppose that Q is a k-by-l pattern such that mr(Q) = 3, MT(Q) < 3 and k + l is a minimum. By minimality, Q has no repeated rows, repeated