JOURNAL OF COMBINATORIAL THEORY, Series A Vol. 24, No. 1, January 1978

Existence of Submatrices with All Possible Columns

J. MICHAEL STEELE

Department of Mathematics, University of 'British Columbia, Vancouver, Canada

Received September 10, 1976

Let M be a matrix with entries from {], 2,..., s} with n rows such that no matrix M' formed by taking k rows of M has s distinct columns. Let f(k; n, s) be the largest integer for which there is an M with f(k; n, s) distinct columns. It is proved that f(k; n, s) = S' rlk (i) (S 1)j. This result is related to a conjecture of Erdbs and Szekeres that any set of 2112 + 1 points in R2 contains a set of k points which form a convex polygon.

1. INTRODUCTION

The theorems provided in this note are motivated by questions like the following:

Suppose an n set x,, X2 .... y X. is colored by s colors in m distinct ways. How large need m be to guarantee that there is (1. 1) a k set colored in all possible (i.e., sk) ways?

Suppose that S is a class of subsets of a set X and that {Xl , X2 .... 1 Xn} is an nelement subset of X for which m of the sets A n {xl , X2 x,,}, A e S, are distinct. How large need (1.2)

m be to guarnatee that there is a kelement set {xil , xi . xi,'I C

{xl , x, x,,} for which there are 2k distinct sets

A Xi,,}, A e S?

The first of these questions is new, but the second has been considered previously. It has in fact been solved quite precisely by Sauer [4] in response to a query of Erdiis. An earlier independent solution was given in [51 in connection with a, probabilistic application, but the result of [5] was not the best possible. In Section 2 of this note Theorem 2.1 gives a general result by a new method which implies these earlier results and covers the fresh ground indicated by question (1.1).

The third section gives a geometrical interpretation to a special case of Theorem 2.1, and shows the relationship of the present work to a longstanding conjecture of Erd6s and Szekeres (see [1, p. xxi]).

84

00973165178102410084$02.0010 Copyright C 1978 by Academic Press, Inc. All rights of reproduction in any form reserved.

EXISTENCE OF SUBMATRICES 85

2. MAIN RESULTS

Let M be a matrix with entries from an ssymbol alphabet {1, 2,..., s}. Now let f (k; n, s) be the largest integer such that there is a matrix M with n rows and f (k; n, s) distinct columns such that no matrix M' formed by taking k of the rows of M has Sk distinct columns.

To note the relationship of f (k; n, s) to question (1. 1) one defines a correspondence between matrices and sets of colorings as follows: M (aij), where aij ~ b and b is the color of xi in the jth coloring of {x, , X2 3 Xn}. For any subset of elements {xi,,xi,,...,xi,,}C{x,,x,,...,xn} there is a corresponding subset of k rows of M which forms a submatrix M'. Further, since any coloring of {xj,~, Xi, Xi,} corresponds to a column of M, the number of distinct colorings of {xi, , xi. xi k } equals the number of distinct columns of M'. In the notation of (1. 1) we therefore have m f (k; n, s) +

The main result can now be stated quite succinctly.

THEoREm 2. 1.

n (n

f(k; n, s) = s'n 1 )(S (2.1)

jk

Proof. First it will be shown by construction that f (k; n, s)

Sn yn k (n)(S 1)nj, and then the opposite inequality will be proved

j j afterward by relating the general case to the first construction.

Define M to be the matrix consisting of all columns such that no column contains k or more ones. Since Eilk (j)(S 1)nJ is precisely the number of

'n

columns with k or more ones, we see that M has Sn Y,k (,D(S Wj

columns. But since no krow submatrix of M contains the column of all

1)ni

ones we have f(k; n, s) >, S" YInk CD(S

To obtain the opposite inequality we suppose that a matrix M has no krow submatrix with Sk columns. Todescribe the columns which are missing from M, let C,, C2,..., C, where (n,) . 7. be a list of the kelement subsets

of the row indices. For each i = 1, 2 . r there is a submatrix Mi formed by

the Cj rows of M. Also by the hypothesis there is a kvector vi which is not

a column of Mj. Now for each such vi let Zi be the set of columns of the

n x sn matrix which equal vi when restricted to the index set Cj . Finally

observe that none of the columns of Z = UT , Zi is a column of M.

If v denotes the number of columns of Mthen V

The proof will be completed by obtaining a lower bound on 1 UT 1 Zi 1.

To do this we define a function on column vectors W = (W, W21 ... 1 Wj as

follows:

0(w) W, where w' (W,', W2 Wn)

(2.2)

86

and

7 ' :C~ 7

~T 1E

~1 EnLE

~ ~.

c Z~ ~and i c 7, 0 :0In

The, funetion has

Jfl

, rst note and t_hell prove

1

i=1

oK1

r, centains all of the ~2 xl

1strieLed ~o G, equal the Jector (1,

,n

1 <

P(Z) 1 >

(S

+4

The proof of (2.4) is immediate since 0 is a function, and (2.5) is just a consequence of (2.3). To prove (2.6) note that if w has k or more ones, then there is a Cj , restricted to to which w has all ones, and hence w e O(Zi), by (2.3) and the definition of Zi. Finally (2.7) comes from (2.6) and easy

counting.

The last calculation is that

n

v < S 1 Z 1 OW1 < sn (S WJ1 (2.8)

j k i

which completes the proof.

The preceding method also permits a precise understanding of those extreme matrices which lack krow submatrices with a complete column set. Such matrices are characterized by a "missing" column vector.

THEOREm 2.2. Suppose M is an nrow matrix with s" I", (~)(s 1)i distinct columns and which has no krow submairix with s11 distinct columns. Then there is an n vector v such that for each column w of M one has wi 0 vi for at least k values of the index 1.

Proof. In the notation of the previous proof, we note that if there is no v as required above then there are vi and vj such that Cj n Cj =~= o yet vi and vj are not equal on Cj n C,. By the definition of 0 and Zi we therefore have 1 O(Zi u Z) I < 1 Zi u Z, J. Consequently, we have 1 O(Z) I < 1 Z 1.

But, since M has Sn YInk (nIXS' 1)1 distinct columns, we note j Z 1 = yn

_ik CjXS 1)n However, by (2.7) we know 1 0(Z)l >,

in

1k (7)(S 1)n~ so the inequality 1 0(Z)l < 1 Z 1 yields a contradiction.

1

87

,c TO A,

one can

This

'r)n

'd o' 19I~ 1933, pLibiisi'ie~i in 1935, promulgated daily,

n s o I ve f.`1 i& k ~~ ~E H, pp. 42; 2; 3j.

IC, of Section 2 are relevant to this conjecture of Erdos and

since they provide a sufficient condition that a set contain a convex

To sce this let X_ be the plane and S the class of convex subsets of 2'.

n A; A c SJI 1

{{Xl ' ~12 1, XW

that 'S, A (Xl 1 X2 1 ... 1 'X,,) is the number of subsets {xi,, xi~ xiJ C

{Xl 1 X2 xn} such that {xl xi . 1VitJ = {Xl 1 X2 XJ n A for some

A c S. Let A~ , j = 1, 2,...1 A(Xl , X2 ... 5 X.), be elements of S such

that each of the sets {x, , X2 Xn} 0 Aj is distinct. These Aj define a

n X A(xl , x. x.) matrix as follows:

aij = 1 if xi c Aj (3.2)

= 0 if xioAj.

By the definition of the Aj we know that M = (ai) has A (Xl 1 X2 ...I X.) distinct columns so

A (Xl , X2 Xn) < f (k; n, 2) (3.3)

unless M has k rows which have 24' distinct columns. But since A(xi 1 ' xi2 Y ... 5 xJ = 2k if and only if the set {xi. ' X2 xi,,} forms a convex polyhedron, we have proved the following:

THEOREm 3.1. A sufficient condition that the set {Xl X, Xn} C R'

contains k points which form a convex polygon is that

k1

(Xl X2 Xn) > 1 n (3.4)

j0

To prove the ErdbsSzekeres conjecture it thus suffices to show that '(3.4) holds when n = 2 k2 + 1. Of course, condition (3.5) has only been proved sufficient and quite possibly the ErMsSzekeres conjecture can be true without (3.4) being met. Still, there are several possible uses of A (xl , x2 x.) in this problem and (3.4) pinpoints the most direct one.

To gain another view of Theorem 3.1 one should note that it is possible

to give a more geometrical proof which av ' oids invoking the full strength

of Theorem 2. 1. For this proof, suppose B c {{Xl , X2 XJ n A: A c S}

88 J. MICHAEL STEELE

and let OB denote the subset of B equal to the elements of B on the boundary of the convex hull of B. We note that 1 aB 1 <_ k 1 if {x, , x, x,,} contains no kelement convex polygon, since, indeed, aB is convex polygon.

yk1 (~)

Next note that there are precisely j=0 J subsets of {x, , X2 XJ with

fewer than k elements. Since aB uniquely determines B we have

k1 (n)

A(xl 1 X21 1 Xj < ~', (3.5)

j=0 j

unless {xl, x,,..., x.,,} contains a kelement subset which forms a convex

polygon. This completes a second proof of Theorem 3.1.

4. A CLOSELY RELATED PROBLEM

In connection with the results given here and the ErdbsSzekeres con

jecture the following question seems quite interesting:

What is the minimum value Of A(Xl 1 X21 ... 1 x,,) given that

{X,, x,,..., xj contains a kset which forms a convex polygon ? (4.1) (The xi are assumed noncolinear.)

If this value is called g(n, k), it is trivial that g(n, k) >, 211, but a sub

stantial improvement on this seems difficult. Still, by consideration of this problem it may be possible to make progress of the yet unreachable con.. jecture of Erd6s and Szekeres.

REFERENCES

1. P. ERD6s, "The Art of Counting" (J. Spencer, Ed.), MITTress, Cambridge, Mass., 1973.

2. P. ERD68 AND G. SZEKERES, A combinatorial problem in geometry, Compositio Math. 2

(1935),463470.

3. P. ERD6S AND G. SWKERES, On some extremurn problems in elementary geometry, Ann.

Univ. Scl. Budapest. E45tvjs. Sect. Math. 34 (19601961), 5362.

4. N., SAUER, On the density of families of sets, J. C ombinational Theory A 13 (1972),

145147.

5. V. N. VAPNIK AND A. YA. CHERVONENKIS, on the uniform convergence of relative

frequencies of events to their probabilities, Theor. Probability Appl. 16 (1971), 264280.

Printed by the St Catherine Press Ltd., Tempelhof 37, Bruges, Belgium.