Subsets of a Finite Set that Intersect Each Other in at Most One Element Citation Keenan, Donald Eugene (1977) Subsets of a Finite Set that Intersect Each Other in at Most One Element. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/xcak-ax60. https://resolver.caltech.edu/CaltechTHESIS:11102025-182244505 Abstract We study subsets of a finite set most of which intersect each other in one element. We first prove a Fisher type inequality of the form m ≤ n. We then investigate those configurations with m = n. Our main theorem is the following generalization of a result due to Ryser . Theorem. Let S 1 ,...,S n be n subsets of an n-set S. Suppose that | S i | ≥ 3 (i = 1,...,n) and that | S i ꓵ S j | ≤ 1 (i ≠ j; i,j = 1,...,n) Suppose further that each S i has non-empty intersection with at least n - c of the other subsets. Then either n ≤ N(c) where N(c) depends only on c, or the incidence matrix A has constant line sums. We then study those configurations for which A has constant line sums and each subset has non-empty intersection with exactly n - 3 of the other subsets. The rows and columns of A may be partitioned into cycles in a natural way. With this we show that A has a cyclic substructure and that the length of any row or column cycle divides the length of the longest cycle. Also, after the rows and columns have been suitably permuted we have AA T = A T A. We relate those configurations with constant cycle lengths to interdependent difference sets, and show that such configurations imply the existence of nonnegative integral matrices satisfying the matrix equation BB T = (k - λ)l + λJ. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Ryser, Herbert J. Thesis Committee: Unknown, Unknown Defense Date: 18 May 1977 Record Number: CaltechTHESIS:11102025-182244505 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:11102025-182244505 DOI: 10.7907/xcak-ax60 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 17752 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 13 Nov 2025 22:09 Last Modified: 13 Nov 2025 22:25 Thesis Files PDF - Final Version See Usage Policy. 14MB Repository Staff Only: item control page

SUBSETS OF A FINITE SET THAT INTERSECT EACH OTHER IN AT MOST ONE ELEMENT Thesis by Donald Eugene Keenan In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1977 (Submitted May 18, 1977) ii Acknowledgements I wish to express my deepest appreciation to my advisor Dr. Herbert J. Ryser. His paper on this problem was the inspiration for much of the work in this thesis. Also, I am most grateful for his patience and encouragement throughout the last four years. My communications with Douglas Leonard were extremely helpful and his interest and ideas on the subject were very much appreciated. I am indebted to Caltech for its financial support in the form of teaching assistantships and for the outstanding research environment it provides. The excellent typing of this thesis was done by Ida Abe and I thank her for her efforts. Finally, I want to thank my wife, Trudy Bergen,for the many sacrifices she has made for my benefit. She also was most helpful as someone I could talk to about new ideas and help get them straight in my own mind. iii Abstract We study subsets of a finite set most of which intersect each other in one element. m < n. We first prove a Fisher type inequality of the form We then investigate those configurations with m = n. Our main theorem is the following generalization of a result due to Ryser . Theorem. Let s , ... ,Sn be n subsets£!. an n-set S. 1 Suppose that s.1 > 3 (i = l, ... ,n) and that I s.1 n s.J I -< 1 (if j; i,j = l, ... ,n). Suppose further that each Si has non-empty intersection with at least n - c of the other subsets. Then either n .::_ N(c) where N(c) depends only on c, or the incidence matrix A has constant line sums. We then study those configurations for which A has constant line sums and each subset has non-empty intersection with exactly n - 3 of the other subsets. The rows and columns of A may be partitioned into cycles in a natural way. With this we show that A has a cyclic sub- structure and that the length of any row or column cycle divides the length of the longest cycle. Also, after the rows and columns have been suitably permuted we have AAT = ATA. We relate those configurations with constant cycle lengths to interdependent difference sets, and show that such configurations imply the existence of nonnegative integral matrices satisfying the matrix equation BBT = (k A)l+AJ. • iv Table of Contents page CHAPTER I: Introduction 1 CHAPTER II: Fisher Type Inequality 3 CHAPTER III: The Case n = m 8 CHAPTER IV: Determination of N(3) 18 CHAPTER V: The Case c=3 with Constant Line Sums 29 CHAPTER VI: Configurations with Constant Cycle Sizes 45 CHAPTER VII: Summary 53 -1- CHAPTER I Introduction Let s , . .. ,Sm be m subsets of an n-set S. 1 In this paper we will deal only with subsets such that the cardinalities of the set intersections satisfy s.l. n s.J I .::_l (i-:/: j; i,j = 1, ... ,m) and most of the S. l. (1.1) n S.J have cardinality one. We will prove a Fisher type inequality of the form m < n. be especially interested in the case of m = n. We will Ryser studied these configurations extensively under the condition that each S. have non1. empty intersection with at least n - 2 of the other subsets, or alternatively, that each Si have an empty intersection with at most one other subset. He showed that except for two low order cases such configura- tions are either finite projective planes or symmetric group divisible . 1 d es1.gns. In this investigation we will weaken the hypothesis by requiring that each S. have non-empty intersection with at least n - c of the l. other subsets for some fixed positive integer c. Under these conditions we are able to prove the following theorem. • Suppose that s.l. 1 >3 (i=l, .. . ,n) (1.2) H. J. Ryser, Subsets of a finite set that intersect each other in at most one element, Journal of Combinatorial Theory A, Vol. 17, No. 1, July 1974 , p. 60. -2and that l I s i ns j j < - (ii- j; i,j = 1, ... ,n). (1.3) Suppose further that each Si has non-empty intersection with at least n - c of the other subsets for some fixed positive integer c. Then either (1) n < N(c), where N(c) is~ positive number depending only on c, . l ess t h an 11 c 2 an d N() c is 2 or (2) The following conditions hold. (i) I S.1 I = I S.J I = k, ~ c.onstant (i,j = 1, ... ,n). (ii) Each element of Sis an element of exactly k of the subsets. (iii) All the subsets have non-empty intersections with the same number of other subsets. We remark that configurations (2) above include finite projective planes and symmetric group divisible designs with Al= 0 and A = 1 2 but allow for still other configurations. Finally, we will concentrate on those configurations of (2) above for which all the subsets have non-empty intersection with exactly n - 3 of the other subsets. In this case, the rows and columns of the inci- dence matrix may each be partitioned into cycles in a natural way. We will show that the cycle sizes of the row partition are the same as the cycle sizes of the column partition. We will also prove a divisibility relationship on the sizes of the cycles. -3- CHAPTER II Fisher Type Inequality Let x , ... ,xn denote the elements of an n-set Sand suppose 1 s1 , ... ,Sm are m subsets of S. The incidence matrix A= [aij] of the subsets s , ... ,Sm of Sis defined by 1 a .. = l.J 1 i f x. E s. J (2 .1) l. (i = 1, ... , m; j = 1, ... , n) a .. = 0 i f x. ff. Si l.J J Again we let I Si I = k.l. (i = 1, ... , m) . Thus the sum of row i of A is k .. l. by£ .. J (2.2) We denote the sum of column j of A We note that£. counts the number of occurrences of x. in the J sets s , ... ,Sm 1 J A line of a matrix denotes either a row or a column of the matrix. Two (O,l) matrices are equivalent provided that one is transform- able into the other by row and column permutations. These operations on the incidence matrix correspond to a renumbering of subsets and elements. Thus we frequently do not distinguish between equivalent matrices. We now define a matrix Y by the equation T A A = Y, (2. 3) where AT is the transpose of the matrix A. The matrix Y has the cardinality of S. n S. in the (i,j) position. l. J Suppose these subsets of S satisfy -4- s-l.. n s.J I 1. < 1 - (if: j; i,j = l, . . . ,m). (2 . 4) We let wi denote the number of subsets Sj such that I s.l. n s.J I = 1 (j = l, . . . ,i - l,i + l, .. . ,m). (2 . 5) The number w. is called the intersection count of set S. and is the sum l. l. of row i of Y with k. excluded . l. We now state a theorem by Ryser 2 which is essential for the proof of Theorem 2.2. Theorem 2. 1 . Let them subsets of an I s.l. I = k.l. I1-Set S satisfy (i=l , ... ,m) (2.6) I s.l. n s.J I -< 1 - (if: j; i,j = l, ... ,m). (2.7) and Suppose that the intersection count wi of Si satisfies w > m - k. + 1 i l. (i = l, ... ,m). (2.8) Then m < n. (2 . 9) Now we consider the situation in which each subset has non-empty inter section with at least m - c of the other subsets for some fixed positive integer c. W. > m - C l. - Theorem 2.2. 2 Thus the intersection count satisfies (i = l , .. . ,m) . (2 . 10) Let s , ... ,Sm be m subsets of an n-set S with 1 H. J. Ryser , Subsets of a finite set that intersect each other in at most one element, Journal of Combinatorial Theory A, Vol . 17 , No . 1 , July 1974, p. 60. -5- (i=l, ... ,m) > 3 (2 .11) and I s i ns.J 1· (i -I j; i,j = l, ... ,m). <l - (2.12) Suppose further that for some fixed positive integer c the intersection count wi of set Si satisfies (i = l, ... ,m). (2 .13) Then either (2.14) m < n or there exists a minimal positive integer M(c) depending only on c such that (2.15) m .::_ M(c). We may assume c _::. 3, since for c = 1 and c = 2 Proof. w. 1 satisfies equation (2.8) and, thus m < n. Suppose now m > n. some i = 1, ... ,m. This means m - normalize A so that k first kl columns. in the first k 1 Then by Theorem 2.1 we know wi .::_ m - ki for 1 < m - k. and so k.1 <- c. 1 We may .::_ c and the first row has a 1 in each of the Since w ·> m - c there must be at least m - c l's 1 - columns of rows 2 through m. or more l's in the first k j=2, ... ,m. C 1 columns since then We note that one of , the first k or more l's in rows 2, ... ,m. None of these rows has two 1 I Sin s.j > 1 for some .l m-c columns must have -c- We may assume this is the first column. Including the 1 in the , first row we get Q _::. ~. 1 rows and columns of A so that A takes the form We may arrange the -6- - 1 1 ... 1 o... 0 0 ... 0 0 ... 0 o... 0 1 o... 0 1 ... 1 0 ... 0 0 ... 0 0 ... 0 1 o... 0 . 0 ... 0 0 ... 0 0 ... 0 ... ... ... ... ... . . . . . .. .. .. .. . o... 0 0 ... 0 1 0 ... 0 o... 0 .l o... 0 0 ... 0 o... 0 1. .. 1 o... 0 ... * * * * * (2 .16) 0 0 m Notice that Q < 7 1 and thus Q ~ m 2 1 because ki ~ 3 for each i implies n ~ 1 + 2Q 1 forces n > m. Notice that we may also suppose that Q - (c - 1) > 0 because Q1 - (c - 1) ~ 0 and Q ~~implies m < (c - l)c 1 1 so that (2.15) is valid. Now, row Q + 1 must have a 1 in at least Q - (c - 1) of the 1 1 blocks of columns formed by the l's in the first Q rows of A since, 1 Row Q + 2 must also have at least 1 otherwise, wQ + 1 < m - c. 1 Q - ( c - 1) l's in these blocks. 1 At most orte of these l's is in a column in which row Q1 + 1 has a 1 since, ptherwise, > 1. I sQ1 +l n sQ1 + 2 Continuing in this manner we see that row £1 '+ t, (1 2-_ t 2-_ £1 - (~ - 1)), must have Q - (c - 1) l's in these blocks and at most t - 1 1 of these l's are in columns which contain a Ql + l, ... ,Ql + (t - 1). we already know that 1 Notice that we have 2~ in rows 1 - (c - 1) < Ill because m i\ <z. Now using Q > c - 1, we estimate the number of columns in A by 1 -7- i\ + t which contain a 1 but do not contain a 1 in any of the preceding rows l\ + 1, ... ,Q 1 + (t - 1). There summing the number of c-0lumns of row are at least Q 1 (c - 1) - (t - 1) such l's in row Ql + t. - Since m > n we have + 1. (2.17) Thus we may conclude that Q1 -(c-l) m > }: i = (Q l - C + 1) (Q l - C -t- 2) /2, (2.18) i=l and since 2 1 ~ cm we have m m m > (c - c + 1) <c - c + 2)/2. (2.19) We solve this inequality and find m < 4c 2 - 3c + c /(4c - 3) 2 Thus the theorem is proved. 2 - 4(c 2 - 3c + 2) (2.20) -8- CHAPTER III The Case n = m Let s , ... ,Sm be m subsets of an n-set S satisfying the conditions 1 of Theorem 2.2. We know by this theorem that except for a finite number of configurations the number of subsets is less than or equal to the number of elements in S. We would now like to study those configurations for which equality holds. Some combinatorial objects of great interest fall into this category. The finite projective planes satisfy these conditions for any > 1. C A symmetric group divisible design is a set of n subsets s , ... , Sn of an n-set S that · satisfy the following conditions. 1 (1) Each subset S. of a k-subset of S (i = l, ... ,n). 1 (2) The subsets may be partitioned into b components, where each component contains exactly n/b subsets. (3) Two distinct subsets in the same component have exactly Al elements in common and two subsets in different components have exactly A elements in common. 2 A symmetric group divisible design with A 1 the conditions of Theorem 2.2 for any c > n/b. = 0 and A2 = 1 satisfies A finite projective plane of order t may be used to construct a symmetric group divisible design on the parameters 2 n = t , k = t, b = t, Al= 0, A = 1. 2 (3 . 1) This is done by simply deleting the first t + 1 rows and the first t + 1 columns of the normalized incidence matrix of the plane. -9- We now restate the theorem which will be the principal result of this section. Theorem 3.1 Let s , ... , Sn 1 be n subsets of an n-set S. Suppose that I Si I (i = l, ... ,n) > 3 (3. 2) and that I s.1 n s.J < 1· - 1 (i I j: i,j = l, ... ,n). Suppose further that each Si has non-empty (3. 3) intersection with at least n - c of the other subsets for sowe fixed positive integer c. Then either (1) n < N(c), where N(c) is a positive number depending only on c, and N (c) is less than lc 1 2 , or (2) The following conditions hold. (i) I s.1 I = I s.J I = k,, ~ constant (i,j = l, ... ,n). (3.4) is an element of (ii) Each element of S - - exactly k of the subsets. (iii) All the subsets have non-empty intersection with the same number of other subsets. In terms of the incidence matrix A, the hypotheses of the theorem say that A is square, each row sum of A is greater than or equal to 3, and T AA = D+ J - E (3.5) where Dis a diagonal matrix, J is the matrix of l's, and Eis a (O,l) -10matrix with row sums less than or equal to c - 1. The conclusion is that if n is sufficiently large A has constant line sums and E has constant row sums. If Sin Sj = <P we will say Si and Sj are linked or that Si is a link of S. and vice versa. -- Under the conditions of Theorem 3.1 each J subset has at most c - 1 links associated with it. Two rows of the incidence matrix A will be linked if the subsets associated with each We note that if two rows of A are linked then their inner are linked. product is O. For the remainder of this chapter ··we will assume the set S and its subsets s , ... ,Sn satisfy the hypotheses of Theorem 3.1 and that A is 1 the incidence matrix for these subsets. Recall that k. is the sum of l. row i of A and£. is the sum of column j. J Suppose some column of A has column sum£. Lemma 3.2. -- for constants rands, r --- > O. > n - s --J-r Then n 2_ N(r,s,c), where N(r,s,c) is a positive number , depending only on r, s, and c . By exactly the same method employed in Theorem 2.2 we count Proof. the number of columns of A and we find n > (Q. - Then Q. > J - J n - s J C + 2) /2 . (3 . 6) implies r n > ( C + 1) (£ . - n - s - c + l)(n - s r r C + 2)/2 (3 . 7) and n > t 2 - 2ns + s 2 r 2 - (2c - 3) n -r s + C 2 + 3c + 2)/2. (3.8) -11- As n gets large the n 2 term on the right hand side dominates and the right hand side of (3.8) becomes larger than n. we must have So for (3.8) to hold n _:: N(r,s,c) where N(r,s,c) is a positive number depending only on r, s, and c. Lemma 3. 3. Let Si be ~ subset of S. Suppose in column j of A, that for each subset st linked to s .. aij = 0 and atj = 0 ---1 Then Q. -< k .. - J 1 We may permute the rows and columns of A so that a .. = 0 Proof. 1] is in the (1,1) position and A ass-umes the form . . . 0- ~ 0 0 1. .. 1 1 p * 1· (3. 9) 0 . * * -0 - Each row of P must contain exactly one 1 since these rows of A cannot correspond to subsets linked to Si. each column. However, P- may have at most one 1 in Hence Q. < k .. J - 1 We now define a matrix B = [bij] of order n as follows. and atj = 0 for each st linked to s.' then b .. 1 1] = 1. If aij = 0 Otherwise, b .. = o. 1] The term rank of a (0,1) matrix is the maximal number of l's no two on a line in the matrix. The Frobenius-Konig theorem says the term rank is equal to the minimal number of lines of the matrix necessary to cover -12all the l's. Lemma 3.4. For sufficiently large n, Bis of term rank n. Proof. By Lemma 3.2 it is only necessary to prove that, if B does not have term rank n, it must contain a column with n - s or more l's r for fixed constants sand r with r > 0. First, suppose B has a row of O's. We may arrange the rows of A so that the row of O's in Bis the first row and so that the rows of A linked to this new first row of A are rows 2, ... ,p where p < c. Since the first row of Bis all O's, the column sum in the first prows of A is at least 1 for every column of A. So A takes the following form after permuting the columns. - 1 ... 1 o... 0 0 . . . 0 0 ... 0- 0 ... 0 1. .. 1 0 . . . 0 0 ... 0 . o... o 0 ... 0 p . . . . . . . . o... o . . . . . . (3.10) 0 ... o . 0 ... 0 * * 1. .. 1 * * * * - '- Thus the columns of A have been divided into c or less groups. there must be rows beyond the first prows. If n > c If one of these rows has more than c l's, one of the groups of columns must contain two or more of them. This would mean there are two sets which intersect in more than one element. So some row i of A has c or less l's. Except for the -13rows linked to this row, each row of A must have a 1 in the c or less columns of row i which contain n - C l's. So one of these columns must have + 1 =nor more l's and we are done, when B has a row of O's. C C Suppose B has a column of O's. Look at the corresponding column Suppose it contains t l's. Associate with each 1 the row it is in A. in and all rows linked to that row. Each row must be associated with a 1, since otherwise there would be a 1 in that row of Bin this column. There are c or less rows associated with each 1, son< tc and, thus, n t > -. C Hence we are done when B has a column of O's. We may now assume B has neither a tow of O's nor a column of O's. If B does not have term rank n then B has a minimal cover of e rows and f columns where e + f < n, 0 < e,f < n. (3 . 11) = n -e, f' = n - f. (3.12) e' + f' > n,O < e',f' < n. (3.13) We let e' Then Actually, e' > 1 and f' > 1 because e' = 1 implies f' n and f' = 1 implies e' = n. We normalize B so that B = ~ j where O is the zero matrix of size e' by f'. (3 . 14) The matrix A assumes the form A (3 . 15) -14where Y is of size e' by f' and corresponds to the zero matrix of B. Now, suppose f' < C 2 This implies e' > n - • C 2 • By associating rows with the l's in a column of Y we see that a column of Y and thus some column of A must have n - Finally, suppose f' > C to it. C 2 l's in it. C 2 . Look at row 1 of A and the rows linked The submatrix formed by the intersection of these rows with the first f' columns of A must have column sum at least 1 for each column. Since there are c or less rows in this submatrix, some row, say row Q, of A contains c + 1 or more l's in these first f' columns because 2 f' > c . Y. Suppose a row of A which is not linked to row Q passes through Then it or one of its links must have two l's in the columns that row Q has l's. This contradicts (3.3). So only rows linked to row Q may also pass through Y and thus e' < c and f' n - c. > We arrange the rows and columns of A so that row 1 is still the initial row, the rows linked to it are rows 2, ... ,t where t 2 c, and A is of the form t -- 1. .. 1 0 ... 0 0 ... 0 o... 0 0 ... 0 o... 0 1. .. 1 0 ... 0 0 ... 0 0 ... 0 . 0 ... 0 o. ... o. .. .. o... 0 * . - ... ... o... ... 0... 0 ... 0 o.. . o o... 0 * * 1 ... 1 o... 0 * * * * X The matrix X has n - trows and (3 .16) less than c columns. If X has a row -15of O's then that row of A may have at most c l's and this implies there is a column of A with.!!. or more l's. If X has no row of O's C then it must have a column with n - ~ C - l's. Thus, considering all the possibilities, if Bis not of term rank n 2 n - C there is a column with - - - or more l's. Hence, for sufficiently C large n, Bis of term rank n. Lemma 3.5. There exists an ordering of the rows and columns of A = 2 , ... ,kn = Qn' provided n is sufficiently large. such that \ 1 By -Lemma 3.4 we can arrange the rows and columns of B so Proof. that B has a 1 in every main diagonal p·osition. In terms of A this means aii = 0 and aiQ = 0 for each s2 which is linked to Si(i = l, ... ,n). . .. + k n Therefore, by Lemma 3. 3 Q. < k .. 1 1 so equality holds for each i. Lemma 3.6. If n is sufficiently large, then A has constant line sums. Proof. We need only show that if n is large enough to force B to be of term rank n and if A does not have constant line sums then A contains n - s r Applying Lemma 3.2 then proves this l's in some column. lemma. We permute the rows and columns of A so that k n = Q • n Suppose thqt A does not have all its line sums equal. (3.17) Then we define the integer e by k l = k e > k e+l ' (3 .18) -16where e < n. We let (3.19) where Y is now a matrix of size e' = n - e bye. Suppose row i intersects Y and it and all its links have O's in one of the first e columns, say column j. Then by Lemma 3.3 £. < ki, J - but j < e and i > e which implies£.= k. > k., contradicting k. < k .. . J J 1 J- 1 2 Suppose e > c . By the above argument, if row i passes through Y then in each of the first e columns there must be a 1 in row i or in one So there must be at least c + 1 l's in the of the rows linked to row i. first e columns of one of these rows, say row j. Now if any row not linked to row j intersects Y then it or one of its links must have two or more l's in the c + 1 or more columns in which row j has 1. contradicts (3.3). Thus e' This < c and e > n - c. We now arrange A as in Lennna 3.4 with the first row being a row that passed through Y and rows 2, ... ,t its links, where t _..::: c. is a matrix of n-t rows and c or less columns. Then X As in Lennna 3.4, if X has a row of O's, there is a column of A with at least.!!. l's. C If X doesn't have a row of O's then one of its columns has n - c or more l's. C 2 Finally, suppose e < c . Associate with each 1 in the first column of A the row it is in and all rows .of A linked to that row. If there 2 are less than n - c l's in the first column of A there will be a row of C Y which is not associated with any 1. However, this implies kj > k 1 for some j > e as shown previously and this is a contradiction. Thus column 1 21 th e proo f o f t h e 1 emma . i s competes has at least n - c 1' s, an d th. C Lemma 3.7. If A has constant line sums, then each subset is linked -17to the same number of other subsets. Proof. Suppose A has constant line sums k. Then each has non- empty intersection with exactly k (k -1) of the other subsets. subset is linked ton - 1 - k(k - 1) So each of the other subsets. We notice from the proofs of Lemma 3.4 and Lemma 3.5 that if condition (i), (ii), or (iii) of Theorem 3.1 does not hold there must be a column of A with n ~ c 2 or more l's. Thus by applying Lemma 3.2 we have proved Theorem 3.1. Now we wish to estimate N(c) for a fixed c. only substitute c 2 = To do this we need s and c = r in equ_a tion (3.8) of Lemma 3.2. Solv- ing the resulting inequality gives us n < (6c 2 - 3c + c /2oc 2 - 36c + 1 )/2. (3.20) While this number is not real for c = 1, we see from (3.7) if r = s = c = 1 that if A does not have constant line sums n > ri(n - 1)/2. (3.21) The smallest configuration is of size 7 by 7 so equation (3.21) never holds and all configurations for c = 1 have constant line sums. N(c) < (6c 2 - 3c + c l2oc 2 - 36c + 1)/2 Thus (3. 22) for c > 2 and for c = 1 conditions (i), (ii), and (iii) of Theorem 3.1 hold. Fina1ly we notice that (Sc) 2 > 20c 2 - 36c + 1 (3. 23) and thus a simpler, though less accurate, estimate is 11 2 N(c) < ~ • (3. 24) -18- CHAPTER IV Determination of N(3) We know that all configurations satisfying the hypotheses of Theorem 3.1 for c = 1 have constant line sums and are projective planes. For c = 2 Ryser showed that there are only two configurations without constant line sums. N(2) = 10. One is of order 9 and the other of order 10. 3 So In this section we will show N(3) = 18 by finding the unique largest configuration for c = 3 without constant line sums. Let us recall the situation for c = 3. s1 , ... ,Sn are n subsets of an n-set S such that (4.1) ( i = l , ... ,n) and that (i 'f j, i,j = 1, ... ,n). (4.2) We further suppose that each Si has non-empty intersection with at least n - 3 of the other subsets. this configuration. The matrix A is the incidence matrix for We wish to determine the largest n for which A does not have constant line sums. By letting c = 3 in equation (3.22) we find N(3) > , (45 + 3/73)/2 < 36. Thus if A does not have constant lin (4.3) sums n < 35. As in the proofs of Theorem 2.2 and Lemma 3.2, if a column of A has column sum Q then 2-2 n > i: i = (Q- 2) (Q- 1)/2. (4 . 4) i=l 3H. J. Ryser, Subsets of a finite set that intersect e ach other in at most one element, Journal of Combinatorial Theory A, Vol . 17, July 1974, No. 1, p. 60. / -19This implies the maximal column sum of A is 9 or less since n < 35. We recall that k. represents the sum of row i of A and Q. represents J 1 the sum of column j. We may assume that the maximal column sum occurs in the first column and that the Q l's of column 1 occur in rows 1 1, ... ,Q . 1 We may also assume that the rows have been arranged so that (4.5) and that the rows and columns of A have been permuted so that A is of the form o... 0 0 ... 0 ... 0 . ·• . . . . . . . .. . . 1 0 ... 0 o... 0 o... 0 1 1 •··. 1 -· 1. .. 1 o... 0 1 0 - o... 0 o... 0 . . . . . . . o... 0 0 ... 0 1. .. 1 c2 * * * . . * * * * * * * * * . . D 0 1 o... 0 ... . ... . ... . (4. 6) 0 1 o... o .. . 0 ... 0 1 .. .. .. . .. 0 ... 0 1 B Ck * 1 where D and Bare matrices of O's if they exist at all. - B has at most ~ two rows and the rows of B represen t the subsets which have empty intersection with rows. s . ct ( t=2, ... , k 1 ) is a ma t r 1.x of k2 - 1 columns and Qt - 1 1 We will consider the possible values of Q , the ma ximal column 1 -20sum. Suppose £ k 1 ..::.. 4. If = 4 then also k 2 = 4 and c2, c 3 and c4 have three columns. Thus 1 = 9. Then, since n..::.. 35, we must have k c2, c3, and c4 each have at most three l's. 1 Of all the rows of c2, C3, and c4 at most two are all O's since row 2 has inner propact 0 with at most two other rows. k 1 Thus A has at most 22 rows. = 3, contradicting k If £ 1 = 4. 1 = 9 and k1 = 3, then c2 and c3 have at most eight rows apiece and n above. < 27. This implies k But if n < 19 then k implies k 1 < 3. 2 2 4 and thus n _2 19 by reasoning as < = 3 and this implies n < 17 which in turn This contradicts (4.1). Thus £ Suppose £ = 8. 1 This implies k < 5. most 28 rows which implies k then n < 31 which implies k and contradicting k 2 1 1 = 4. If k 1 Thus £ < 3. Next, suppose £ 1 ~ 4, -; 9. 1 = 5 then k 2 = 5 also, Therefore A can have at contradicting k 1 = 7. = 9 we can show k 1 1 = 5. 1 It follows that n < If k 2 = 3. 2 =4 ..::.. 4. If n < 15 then k 1 < 1 3. =3 How- -I 8. = 3 and n < 15. 1 This forces By the same methods employed for £ n = 15 A may be put in the form 1 21 implying k = 3 then n < 24 and thus k ..::_ 4 implies n < 18 which in turn implies k n < 16 and then k and ~ = 4. 2 1 1 If k 1 - and c , ... ,c each contain at most four l's. 2 5 ever, k But n < 22 implies =8 If -21- -111 00 00 00 00 00 00 11 00 00 00 00 00 00 11 00 00 00 00 00 00 11 00 00 00 00 00 00 11 00 00 00 00 00 00 00 00 00 00 00 00 11 ... ... c2 . .. * * * * * ... ... * ... c3 * * * * 100 100 100 100 100 100 11 (4.7) 010 010 001 .. 001 - 000 000 10 0l 1 0 1 0 1 0 0 1 0 1 0 1 * *- where c 2 has two rows and c 3 has four rows or c 2 and c 3 each have three rows. Now in the rows of A which pass through c 2 there must be a 1 in columns 4, 6, 8, and 10, since otherwise one of rows 2, ... ,5 would have inner product 0 with at least three other rows, contradicting c = 3. then two of these l's must be in the same row of A and thus row 14 has inner product 2 or greater with this row which is impossible. If 2 1 Thus = 6 there must be a row with row sum 5 or less since other- wise 2, < 6 (j = 1, .. . , n) and ki -> 6 (i=l, ... ,n). But since J n n I: £. = I: k. this implies £. = k. = 6 (i,j = 1, .. . , n) and A has l. l. J i=l j=l J constant line sums. So k. l. < 5 for some i and this forces n < 28. Continuing as before we can show no configurations exist for 2 1 = 6. But -22Now suppose £ 1 = 5. There must be a row with row sum 4 or less . This implies n < 19 and thus k 1 < 4. If k 1 = 3, then n < 15 and since we will show N(3) = 18 we need not consider this case further. then we have k = 4, k 2 3 = 4 and k 4 = 4 or 5. If k 4 If kl= 4 = 5 then A may be put in the form -1111 000 000 0000 00001000 1000 1000 1000 111 000 000 000 000 111 000 000 0000 0000 1111 0000 0000 0000 0000 1111 0000 0000 100 010 100 010 1000 0100 1000 **00 0100 0100 0100 0100 100 010 001 000 * * * 0010 0010 0010 0010 100 010 001 000 * * * 0001 0001 0001 100 010 001 * * * - (4.8) - If there is a 1 in position (7,15), then filling in. the rest of matrix under the given conditions leads to a contradiction. If there is a O in position (7,15) we may assume there is a 1 in position (7,16) and a 1 in position (18,8) or position (18,10). If position (18,8) has a 1, then we are again led to a contradiction. However , if there is a 1 in position (18,10) then A may be filled out and the only possibili ty for A up to row and column permutations is -23- -1111 000 000 0000 00001000 1000 1000 1000 111 000 000 000 000 111 000 000 llll 0000 0000 0000 0000 llll 0000 0000 100 010 100 010 1000 0100 1000 0100 0100 0100 0100 0100 100 010 001 000 000 001 100 010 0001 0010 0100 1000 0100 1000 0010 0001 0010 0010 0010 0010 100 010 001 000 001 000 010 100 0100 1000 0001 0010 0001 0010 1000 0100 0001 0001 0001 100 010 001 010 100 001 0010 0001 1000 0010 0001 0100 - No configuration exists when k Thus, (4 .9 ) is 0000 0000 4 = (4.9) .. - q and if £ 2 2. 4 then n 2. 12. the unique largest matrix . without constant line sums for c = 3 and thus N(3) = 18. A quick check of the inner products of the rows of this matrix reveals that it does indeed satisfy the hypotheses of Theorem 3.1. Each of the nine rows with row sum 5 has inner product 1 with every other row. The nine rows with row sum 4 may be put in three groups with three rows each where each row has inner product 0 with the other rows in its group and inner product 1 with all the remaining rows . is true for the inner products of the columns. The same We may rearrange the rows and columns so that the first nine rows have row sum 4 and the first nine columns have column sum 4. Also we may put the rows which have inner product 0 with each other into blocks of three and likewise the columns. When A is in this form we have -24- -400 040 004 400 040 004 400 040 004 T T AA =A A= (4.10) 5 5 5 5 5 5 5 5 -- 5 - where all the remaining entries are l's. We notice that this is a hybrid of the symmetric group divisible design with v = 15, k = 4, b = 5, Al= 0 and A = 1 and the projective plane of order 4 whose incidence 2 matrix is of order 21. The order of A is exactly the average of the orders of these two designs and the rows with row sum 4 behave like rows of the symmetric group ,divisible design while the rows with row sum 5 behave like rows of the plane. A may be obtained from the plane by permuting rows and columns until the first three rows and columns are of the form -25110 101 011 111 000 000 000 000 000 000 111 000 000 000 000 000 000 111 000 000 000 100 100 100 010 010 010 001 001 001 (4.11) A 000 000 000 000 000 000 000 000 000 If the first three rows and the first three colu1nns are now deleted the resulting matrix A will now satisfy (4.10) and is thus equivalent to the matrix in (4.9). We notice that from any projective plane of order t we may delete three rows and columns as in (4 . 11) to obtain a configuration satisfying the hypotheses of Theorem 3.1 for c = t - 1 with c columns. 2 + 3c rows and No larger configuration without constant line sums is known for any c so it has been conjectured that N(c) = c 2 + 3c. 4 A may also be obtained from the previously mentioned symmetric group divisible design whose incidence matrix is 4 D. E. Keenan, D. A. Leonard , Qn a theorem of Ryser, Journal of Combinator ial Th e ory A, to a pp e a r . -26- -000 100 100 100 100000 000 010 001 010 001 010 001 010 001 100 010 001 000 000 000 100 010 001 010 001 100 001 100 010 100 C = 010 001 100 010 001 000 000 000 001 100 010 010 001 100 100 010 001 001 100 010 010 001 100 000 000 000 100 010 001 100 010 001 010 001 100 001 100 010 100 010 001 000 000 000 - (4.12) - We can border C with three new rows and three new columns to obtain 100 010 001 000 000 000 000 000 000 111 000 000 000 111 000 000 000 111 000 000 000 A= 000 000 000 100 100 100 010 010 01 0 001 001 001 which satisfies (4 . 10) . (4 . 13) C -27One matrix of order 17 is known which satisfies the given conditions. It may be obtained from (4.13) by simply deleting the first row and first column. We then have a matrix B of order 17 which satisfies - ,..... 40 04 400 040 004 400 040 004 400 040 004 5 5 5 c; J 5 5 - ._ where all other entries are l's. By deleting the first two rows of (4.13) we have a matrix D of order 16 again satisfying the hypotheses of Theorem 3.1. We see - .... 4 400 040 004 400 040 004 T T D D=DD = ,. 400 040 004 400 040 004 5 - 5 5 - where all the remaining entries are l's. (4 . 15) -28We note that since the matrix C in (4.12) is symmetric, the matrices A, B, and D of (4.13), (4.14), and (4.15) respectively are also symmetric. Also, in these examples, then they have the same row sum. if two rows have inner product 0 These properties do not necessarily hold for configurations of lower order. To see this we look at the matrix ,- E = - 00 00 1111 0000 0 1 1111 1111 11 0000 1 0000 10 10 10 10 1000 0100 0010 0001 0 0 0 0 1000 0100 0010 0001 01 01 01 01 1000 0100 0010 0001 0 0 0 0 0100 0100 0001 0010 ~ (4.16) - E has a column with column sum 2 but no row with row sum 2. Thus no permutation of rows and columns could transform E into a normal matrix let alone symmetric . Also row 1 and row 2 have inner product 0 but row 1 has row sum 4 and row 2 has row sum 5. -29CHAPTER V The Case c = 3 with Constant Line Sums We now turn our attention to those configurations which satisfy conclusion (2) of Theorem 3.1 with c = 3. Thus if A is the incidence matrix of such a configuration then A has constant line sums and each row of A has inner product 1 with exactly n - d of the other subsets, where J = 1, 2, or 3. If d = 1 then the configuration is a finite pro- If d = 2 the configuration is a symmetric group divisible jective plane. design on the parameters n = k 2 - k + 2, b = (k 2 - k + · 2)/2, >.. 1 = 0, >.. 2 = 1, (5.1) where k is the cardinality of each of the subsets and bis the number of distinct components of the design. exist for n = 8 and n = 14. 5 Thes~ configurations are known to We will not concern ourselves further with these configurations. We now concern ourselves only with those configurations for which each row of A has inner product 1 with exactly n - 3 of the other rows. Equivalently, each subset S. of S has non-empty intersection with l. exactly n - 3 of the other subsets. For the remainder of this chapter the matrix A will be the incidence matrix of a configuration satisfying conclusion (2) of Theorem 3.1 in which each subset has non-empty intersection with exactly n - 3 other subsets . Thus A is any (0,1) matrix of order n which satisfies AAT = (k - 1) I+ J - E, (5.2) 5R. C. Bose, S.S. Shrikhande, and K. N. Bhattacharya, On the construction of group divisible incomplete block designs, Ann. Math. Statist. , Vol . 24, 1953, p . 176. -30where k > 3 and Eis a syrmnetric (0,1) matrix of order n with all line sums equal to 2 and with O's in each of then main diagonal positions. If we let k denote the sum of each line of A then, since no two rows have inner product greater than 1, each row of A has inner product 1 with exactly k(k - 1) of the other rows. n = k 2 Thus we may conclude that - k + 3. (5. 3) No two columns of A have inner product greater than 1 since this would imply there are two rows with inner product greater than 1. column of A has inner product 1 with exactly other columns. So each k(k - 1) = n - 3 of the Thus AT is also the in~_idence matrix of a configuration satisfying these required conditions. One of the main conclusions of this chapter will be that the rows and columns of A may be permuted so that (5.4) A matrix satisfying equation (5.4) is said tc be normal. To study the structure of A we need to arrange the rows and columns of A in an appropriate order . We recall the definition that rows are linked if their inner product is O. columns. We apply the same definition to the Since each row is linked to two others, the rows may be grouped into cycles with each row linked to the rows immediately preceding and following itin the cycle . also linked . The first and .last rows of each cycle are Likewise, the columns may be grouped into cycles. If the rows and columns of A have been arranged in cycles in this manner then we say that A is cyclically normalized. If A is cyclically normalized the matrix E in equation (5.2) is of the form -31- E = (5. S) where each E. is a square matrix of order n. and l. 1. 1 0 1 1 E. = = l. (C l. 1 1 1 n. + c-1). n. (5.6) 1 0 is Furthermore, all the remaining entries of each E. and E are 0, C 1 ni the circulant permutation matrix of order n. with a 1 in the (1,2) posil. tion, and n 1 + ... + nt = n. Each E. corresponds to a row cycle of l. size n., the number of rows in the cycle. l. A cycle may contain as few as three rows or as many rows as there are in the entire matrix. Examples are known for these extreme cases. If each cycle contains exactly three rows then A is the incidence matrix of a symmetric group divisible design on the parameters n = t2 - t + 3 , k === t , b = (t 2 - t + 3) I 3, A =0, A =1. 1 These _designs are known to e xist fo r n = 9, 15 , and 45. 2 6 For examples which have only one cycle encompassing all the rows of the mat r ix we use the idea of planar near difference sets of type 2 as defined by Ryser. Suppose D = {d , ... , dk} is a set of k residues 2 1 modulo n (n ~ 4) with the property that for any residue a "1- 0,±1 (mod n) 6 R. C. Bose, S . S. Shrikhande, and K. N. Bhattacharya, On the construction of group divisible i ncomplete block designs , Ann . Math . Statist ., Vol. 24 , 195 3, p . 176 • -32the congruence d. - d. J 1 = a (mo,d n) has exactly 1 solution pair (d.,d.) with d. and dJ. in D and no solution 2 1 J l. pairs for the residues a ence set o f ~ 2. (5. 7) = ± 1 (mod n). Then D 2 is a planar near differ- Now the incidence matrix for D is 2 (5.8) where C is the circulant permutation matrix of order n with a 1 in the (1,2) position. Hence we have (5.9) and AA T = (k - 1) I - J - -1 (C + C ). (5 .10) Planar near difference sets with k > 3 are known to exist for n = 9, 15, and 23. 7 The sizes and relationships of these row and column cycles are the objects of our investigation of these configurations. A submatrix of a cyclically normalized incidence matrix formed by the intersection of the rows of a row cycle and the columns of a column cycle is called a section. We call an r bys matrix B = [b .. ] a right shift matrix if whenever l.J e = i + 1 (mod r) , f = j + 1 (mod s) (5 .11) then (5.12) 7 H. J. Ryser, Variants of cyclic difference sets, Proc. Amer. Math. Soc., Vo l. 41, No. 1, Nov.1973, p . 49, -33Bis called a left shift matrix if whenever e _ i + 1 (mod r) , f = j - 1 (mod s) (5 .13) then - (5.14) For example, and l O1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 (5.15) are right shift matrices and is a left shift matrix. We notice that reversing the ~yclic order of the rows (columns) of a right shift matrix transforms it into a left shift matrix and vice versa. Theorem S. 1. Suppose that B is an r bys section of ~ cyclically normalized incidence matrix A. Proof. We may assume that Bis the intersection of the first r rows and the firsts columns . B / O. Then Bis~ right or left shift matrix If B = 0 it is a shift matrix so we may assume By cyclically permuting the rows and columns we may move any 1 in B to the (2,2) position with A still cyclically normalized. This row 2 is linked to row 1 and row 3 and column 2 is linked to column 1 and column 3. Suppose now that there are O's in positions (1,1) and (1,3). In that case we permute the rows and columns of A other than the first -34three rows and the first three columns so that A is of the form 0 0 0 0 1 0 1 0 1 - 0 .... 0 0 *0 * 0 1 0 p * * * (5.17) 0 1 0 0 0 where Pis a submatrix of k - 1 rows and k columns. No column passing through Pis linked to column 2 so each column of P contains a 1. ever, this means some row of P contains more than one 1. How- But this contradicts the hypothesis that the inner product of any two rows is at most 1. Hence there must be a 1 in position (1,1) or position (1,3) . Likewise, for any two entries in adjacent corners of the initial 3 by 3 matrix at least one of them is a 1. Hence each 1 ln B must have l's immediately before it and after it in either the right shift direction or the left shift direction. We will now need a short lemma before finishing this proof. Lemma 5.2. Suppose that three consecutive rows of a row cycle and three consecutive columns of a column cycle intersect~ form~ submatrix of one Ei_ the following types: (5.18) -35Then this submatrix is --------- ~ ~ ~l (5.19) ~l~ Proof. We may assume this subrr~trix is made up of the first three rows and columns of A. Suppose the submatrix is of the first type shown in (5.18) and there is a O in the* position. We may permute the remain- ing rows and columns of A so that A is of the form ~ 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 * 0 1 0 .• . .• p * * * (5.20) 0 1 0 - * - where P has k - 2 rows and k - 1 columns. There must be at least one 1 in each column of P and no more than one 1 in each row of P. This is a contradiction so that there must be a 1 in the* position. The proof is the same for the other matrices in (5.18). Now we return to the proof of Theorem 5.7 . By reversing the cyclic order of the rows in this row cycle, if necessary, we may assume the main diagonal of this initial 3 by 3 matrix is all l's. We claim that now the right shift diagonal of B through these three l's is, in fact, all l's. If not, then continuing in the right shift direction we must encounter a first 0. Since each 1 in B must have l's immediately before and after it in either the right shift direction or the left shift direction we must -36then have a submatrix of three consecutive rows and columns which looks like where the above mentioned O is in the lower right hand corner. applications of Lemma 5.2 give Now two us a submatrix 0 Ol~ 1 0 (5.22) U 1 0 1 where the 1 in the lower right hand corner of (5 . 22) is the 1 in the center of (5.21). than 1. But now two rows of A must have inner product greater Thus for each 1 in B either the right shift diagonal through it or the left shift diagonal through it is all l's. If the right shift diagonal through some 1 in Bis all l's and the left shift diagonal through some 1 in Bis all l's, then these diagonals cross each other and there is a submatrix of the form lOU 0 1 0 [1 0 1 (5.23) or which is a contradiction. Thus the shift diagonal of l's through each 1 of B must go in the same direction and thus Bis a shift matrix. Finally, we show that if B # 0 then rls or sir. since otherwise we may consider AT. We may assumer< s We may a lso assume there is a 1 in position (1,1) and the right shift diagonal through (1 , 1) is all l's , Let s = ar + b, 0 < b < r. (5.24) -37If b :/: 0 then there is a 1 in position (1, r + 1) and there is a 1 in position (b + 1, 1). There is also a 1 in position (b + 1, r + 1) since b + 1 - s + r + 1 (mod r)and r + 1 = s + r + 1 (mods). However, row 1 and row b + 1 now have inner product greater than 1 so that b = 0 and r Is. Corollary 5. 3. Suppose that B is an r bys section of A with B 'f 0 and s = a: r, where a > 1. sums of B equal a. Then all column sums of B equal 1 and all row Likewise, if r = as, where a> 1, then all row sums of B equal 1 and all column sums of B equal a. Proof. Assume first that s = ar, . where a > 1. Then by Theorem 5.2 Bis a shift matrix so that B has equal row sums and equal column sums. We may assume Bis a right shift matrix and there is a 1 in the (1,1) position of Band also in position (1, r + 1) since r + 1 = 1 (mod r). If there is another 1 in column 1, say in position (m,l), there is also a 1 in position (m, r + 1). m have inner product greater than 1. Hence B has column sums 1 and thus the total of the r equal row sums is s. If r = But now row 1 and row Hence each row sum is a= s/r. as, where a> 1, we simply consider AT and apply the above proof. Corollary 5.4. a and b. Suppose that A has two row (column) cycles of sizes Suppose also that a column (row) cycle of size c with c > max (a,b) forms a non-zero section with both of these row (column) cycles. Then c is the least common multiple of a and b. Proof, By Theorem 5.2 c is a multiple of both a and b. d = lcm(a,b) and suppose c > d. Let We may assume both sections are right shift matrices and each has a 1 in position (1,1). \ However, d + 1 = 1 (mod a) and d + 1 = 1 (mod b) so each section also has a 1 in position -38(1, d + 1) and the rows of A corresponding to the first row of each section have inner product greater than 1. Corollary 5.5. Thus we have c = lcm(a,b). Suppose that A has two row (column) cycles of sizes a and b with (a,b) = 1. Then only one column (row) cycle forms non- zero sections with both of these row (column) cycles and this column (row) cycle is of size ab. Proof. At least one column cycle forms non-zero sections with both row cycles since otherwise each row of one cycle would have inner product 0 with any row of the other cycle. Suppose a colu1111.7. cycle of size c forms non-zero sections with both row cycles. or clb by Theorem 5.1. However, since (a,b) and thus by Corollary 5.4 c = lcm(a,b) = ab. Then ale or cla and hie = 1 we ~ust have ale and hie By Corcllary 5.3 the sec- tion with a rows has row sums band the section with brows has column sums 1. Since no two rows may both have l's in the same two columns, for any_ row in the section with a rows and any row in the section with brows there is exactly one column of this column cycle which has a one in both of these rows. If any other column cycle forms non-zero sections with both of these row cycles we must have rows with inner product greater than 1-. Thus this column cycle of size ab is the only one forming non- zero sections with both of these row cycles. Theorem 5.6. The rows and columns of A may be permuted so that AAT = ATA. Proof. Cyclically normalize A and arrange the row cycles in order of increasing size from top to bottom and arrange the column cycles in order of increasing size from left to right. AA T = (k - 1)1 + J - E, Then (5.25) -39where Eis of the form E = (5.26) In (5.26) each Ei corresponds to the i the number of rows in this row cycle. th row cycle and its order ni is Each E. has the form 1 -1 C . E. = C 1 n. + ni 1. (5. 27) Also, we have where E' is of the same form as E except there may be a different number of blocks E~ and their sizes may be different from the blocks in E. 1 Each E~ now corresponds to a column cycle and its size is the number of 1 columns in the cycle. Thus if we show that there are the same number of row cycles of a given size as column cycles of that size, then AAT = ATA for A in this cyclically normalized form. It suffices to show that there are at least as many column cycles of a particular size as row cycles of that size, since applying this to AT gives us the reverse inequality. We need only show this for cycles of size greater than 3 since if there are the same number of row and column cycles for all sizes greater than 3 the remaining rows and columns must belong to ~ycles of size 3 and there must be the same number of each of these because the number of rows equals the number of columns·. Suppose there is a row cycle of sizer> 3. We may make this the first row cycle of a cyclically normalized A, no longer requiring that -40the cycles be kept in order of increasing size. If Bis a non-zero section formed by this row cycle and a column cycle of sizes< r, then sir and Bis a shift matrix with a single 1 in each row. Thus the only rows of B which have a 1 in the same column as the 1 in row 1 are rows 1 + s, 1 + 2s, ... , l + r - s. column. Since s > 3 row 3 does not have a 1 in this If Dis a non-zero section formed by this row cycle and a column cycle of sizes> r, then D has only one 1 in each column and no column of D has l's in both row 1 and row 3. However, since r > 3 row 1 and row 3 of A must have inner product 1 so there must be a column cycle of sizer in which there is a column with l's in both row 1 and row 3. If there are fewer column cycles of sizer than row cycles of size r then there must be two row cycles such that their first and third rows both contain l's in a column of the same column cycle. However, by cyclically permuting the rows and possibly reversing their cyclic order both the sections can be made right shift matrices with l's in the first and third rows of the first column of each. Then the third row of each section has l's in the first and third columns. This is a contradiction, thus there are at least as many column cycles of sizer as row cycles of sizer and the theorem is proved. Theorem 5.7. cycles of A. Lets be the size of the largest row and column If r is the size of any other row or colum.'1 cycle of A then rls. Proof. Since the row cycle sizes and column cycle sizes are the same we need only show this is true for row cycles. row cycle of sizer, where r does not divides. Suppose there is a Given any row cycle of sizes there can be at most one column cycle which forms non-zero -41sections with both of these row cycles. This is because the size of any such column cycle must divider ands since if it were of sized with r . < d < s then r Id and d Is so r Is. of sizes a and b with a,b < r If there were two such column cycles < s then by Corollary 5.4 r = s = lcm(a,b). If no column cycle forms non-zero sections with both row cycles then each row of one cycle has inner product O with each row of the other cycle. If only one column cycle of size a forms non-zero sections with both row cycles then each row of the r-cycle has inner product O with some of the rows of the s-cycle. Theorem 5.8. In either case we have a contradiction so that rls. Let a be the number.of row (column) cycles of A whose size is even and let b be the number of row (column) cycles of A whose Then b ~ ~ odd integer and for k > 3 size is odd. ---Proof. Since n = k 2 a is an even number. ------- - k + 3 is odd and n is the sum of the row cycle sizes there must be an odd number of odd cycles. of AAT must be a square since det (AAT) det (AAT) we first look at AAT - J = [det (A)] 2 . = (k - form described in (5.26) and (5.27). l)I - E, The determinant To evaluate where Eis of the Thus MT - J is a matrix which is all O's except for blocks down the diagonal of the form . (k - l)I r - C . - C-l r r ' h • were eac h row eye 1 e o f sizer correspon d s t o an r by r block. The eigenvalues of a block corresponding to a row cycle of sizer o - o-1 ,(k - 1) - o2 - o-2 , ... , (k - 1) - u~r - o-r , where o is a primitive r th root of unity. Since (k - 1) - oi - o-i = are (k - 1) - or-i ·- o-(r-i) • each eigenvalue has multiplicity two except for r r r/ -r/2 (k - 1) - o - o- = k - 3 and, if r is even, for (k - 1) - o 2 - o (k - 1 ) - = k + 1. Thus if r is odd the determinant of the block equals --42r-1 -r (k - 3)( IT (k - 1 - oi - o-i )) 2 . i=l However, is a product of algebraic integers and their conjugates and is therefore the product of the norms of algebraic integers, which is an integer. Hence if r is odd there is an integer c such that det ((k - 1) I r - C r c-r 1 ) = (k - 3) c 2 . r - C r c-r 1 ) = If r is even then det ((k - 1) I where is an integer. Hence if r is even there is an integer d such that det ((k - 1) I r - C r c-r 1 ) = Thus we may conclude that det (AAT - J) Now AA T = (k - 3)a+b (k + l)a h 2 . - J and J can be mutually diagonalized by a theorem of -43Hoffman , since AA T has constant line sums. 8 The matrix J has eigen- 2 values n =k -k + 3 of multiplicity 1 and 0 of multiplicity n - 1. The column vector of all l ' s is associated with the eigenvalue n of J and the eigenvalue k - 3 of AAT - J. for some integer m. Hence we have Fork> 3 this integer is a square if and only if a is even, and the proof is complete. We remark that Theorem 5.8 does not hold fork= 3. The incidence matrix A = 100 010 001 100100 010010 001001 100 010 001 100 010 001 010001 101000 010100 001010 000101 100010 (5.28) satisfies the given conditions , but A has one row cycle of size 3 and one row cycle of size 6. The only other known configuration with any even cycle is 8A. J. Hoffman, On the polynomial of a graph, Amer. Math. Monthly, Vol. 70 , 1963 , p . 31. -44- .... A= - 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 , .1. 0 0 0 1 0 1 0 0 0 1 0 0 0 1 , .1. 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 - (5.29) - which has one row cycle of size 3 and two row cycles of size 6. In fact these two configurations are the only ones we know which do not have all their cycles of the same size. - 45CHAPTER VI Configurations with Co£1stant Cycle Sizes We now look at those configurations satisfying conclusion (2) of Theorem 3.1 in which each subset has non-empty intersection with exactly n-3 other subsets and, in addition, all of the cycles of a given configuration must be of the same size. monocyclic. We will call such configurations For the remainder of this section A will be the incidence matrix of such a configuration. We will first relate these monocyclic configurations to another combinatorial object called a (v,k,A)-design. A (v,k,A)-design is a collection of v subsets s , ... ,Sv of av-set 1 S such that s.1 =k (i = l, ... ,v), (6.1) and s.1 n s.J I = >, where O < A < k. (i,lj; i,j=l, ... , v), (6.2) If B is the incidence matrix of a(v,k,A)-design, then Bis av by v (0,1) matrix satisfying BBT = (k - A)l + AJ. (6.3) These designs and related matrix equations have been very heavily studied and we will use a non-existence theorem by Hall and Ryser to obtain a non-existence theorem on monocyclic configurations. Theorem 6.1. Suppose there exists~ monocyclic configuration with line sums k and cycle sizes r, r < n. Then there also exists av by v matrix B of non-negative integer entries and constant line sums k satisfying (6.4) -46where v = (k Proof. 2 - k + 3)/r, k' = r - 3 + k, A= r. (6.5) Let A be the cyclically normalized incidence matrix for the monocyclic configuration. • • intersection o f t he i th Let A .. denote the section of A formed by the l] th row eye 1e an d t h e J• co 1umn eye 1 e. Since A .. i] is a square shift matrix of order r it has constant line sums, say b ... iJ 2 Let v = n/r = (k - k + 3)/r be the number of row cycles. We form the v by v matrix B = [b .. ] . iJ Since A has constant line sums k we have V V E bi.= k (i=l, ... ,v), j=l J }; b i=l . . iJ = k ( j = l , . . . , v ) . (6.6) Each row of A has inner product 1 with r - 3 of the rows in the same cycle. In a section with constant line sums b .. each row has inner i] product 1 with b .. (b .. - 1) of the other rows. iJ iJ Thus we have V E b .. (b. . - 1) j=l iJ iJ =r - (6. 7) 3, and by (6.6) V E j=l 2 b .. = r - 3 + k. iJ (6.8) Each row of A has inner product 1 with all r rows of any other eye 1e. • he p Cons id er a row int th row eye 1e an d t h e rows o f t h e q • • o f t h e J• Th e intersection row eye 1 e. cycles accounts for b .b . PJ qJ th th • h ese two row co 1 umn eye 1 e int of the v inner products which equal 1. Thus for p / q we have V E b .b . = r. j=l PJ qJ (6.9) -47The arguments are the same for column cycles so by equation (6.8) and (6.9) we have BTB = BBT = (k - 3)r + rJ. (6.10) We let r = A and k' = r - 3 + k and the theorem is proven. We will now use the following theorem byHalland Ryser. Theorem 6.2 (Hall-Ryser) odd. 9 Let H be~ matrix of order v, where vis Let H have the integer k' in the main diagonal positions, and the integer A in all other positions, where O < A < k'. If there exists a matrix B with rational elements such that (6.11) then there must exist an integer T such that T 2 = (k' - (6.12) A)+ VA, Moreover, the Diophantine equations (6.13) and 2 2 (v - 1) /'!. 2 x 2 = (k' - A) Yz + (-1) vz 2 (6.14) must each possess solutions in integers not &11 zero. If there exists a monocyclic configuration with line sums k > 3 and cycle sizes r, then there exists a matrix B with non-negative integer elements satifying equation (6.11) with v = (k and A= r. - k + 3) /r, k' = r - 3 + k, We notice that (k' - A)+ VA= r - 3 + k - r +~(k so that equation (6.12) is always satisfied. 9 2 2 - k + 3)/r)= k 2 (6.15) By using these parameters Marshall Hall, H. J. Ryser, Cyclic incidence matrices, Can. Jour. of Math., Vol. III, No. 4, 1951, p. 495-496. -48in equations (6.13) and (6.14) we obtain the following. Corollary 6.3. Suppose there exists~ monocyclic configuration with line sums k > 3 and cycle sizes r, where r . < n. Then the Diophan- tine equations (6.16) and (6.17) must each possess~ solution of integers not all zero. We note that fork= 6 and r = 3 or 11 Diophantine equations (6.16) and (6.17). solutions exist to the Yet no monocyclic configura- tions exist with these parameters. Fork= 9 and r = 15 equation (6.17) becomes x 2 2 2 = 6y + 5z , 2 2 2 (6.18) which has no nontrivial solution. Fork= 9 and r = 25 equation (6.16) becomes x 2 = 6y 2 2 - 25z , 1 1 (6.19) which has no nontrivial solution. So there are no monocyclic configura- tions with line sums 9 and cycle sizes 15 or cycle sizes 25. For all other admissible parameters k and r with k < 14 equations (6.16) and (6.17) possess nontrivial solutions. The monocyclic configurations which have only one cycle of size n = k 2 - k + 3 are equivalent to planar near difference set of type 2 as described in section 5. shift matrix and thus This is because A may be taken to be a right -49(6.20) and (6.21) Ryser proved that if a planar n£ar different set of type 2 of k integers (mod m) exists such that n is divisible by 3 then the Diophantine equation (6.22) must have a solution in integers x,y, and z not all zero. We now define a variation on these near difference sets. Let k be an integer with k ~ 3 and let r be an integer with r ~ 3, such that r divides n = k 2 - k + 3. Let D.. (i,j = 1, ... ,n/r) be (n/r) 1] 2 subsets of distinct integers modulo r, possibly empty, such that r E j=l lni3.I = k (6.23) (i = l, ... ,r). Suppose that for each i (i = l, ... ,r) and each a 1- 0, ±1 (mod r) (6.24) d (l)_ d(Z)= a (mod r) ij ij Dij f or some j. • h as exac tl y one Solut1·on w1"th d(l) ij' d(Z)E ij Suppose a 1so that for each i and Q (if £;i,£ = l, ... ,r) and each residue a (mod r) the congruence has exactly one solution with dijEDij and dQj E DQj" sets, Dij' a (k,r) near difference partition. For example, a (4,5) near difference partition is We call these -50- Dll = {1,3}, n = · {l}, D = {l}, 12 13 n D21 = {l} n = {3,5}, n23 = {2}, (6.26) {l} , n = {2}, n = {3,5}. 32 33 = 31 22 Theorem 6.4. If there exists~ (k,r) near difference partition then there also exists~ monocyclic configuration with line sums k and cycle sizes r. Proof. We form an n by n matrix A from the near difference parti- tion as follows. Let Al!!_ r All A = (6.27) A A nn ¥,1 'Tr where each Aij is an r by r matrix of the form dq) A .. = C 1J 1J (1) (t) 1J 1J + ... + Cd~~) 1J (6.28) where d . . , .•. ,d .. are the elements of D.j and C is the r by r circulant permutation matrix with a 1 1 in the (1,2) position. We note that (6.29) Thus, if i I j then by (6.25) r-1 • I + C + ... + C = J, (6. 30) -51where J is the r by r matrix of l's. If i = j then by (6.23) and (6.24) (6.31) But then we have AAT = (k - l)I + J - E, (6.32) where A, I, J and E are n by n matrices and E has all zero entries except 1 for.!!. blocks of sizer by r down the diagonal of the form (C + c- ). r Thus A is the incidence matrix of a monocyclic configuration. We remark that all that is needed to prove the converse of Theorem 6.4 is that A may be arranged so that all its sections are right shift • matrices. j th If sot h en A.. , t h e section • f orme db y t h e i• th row eye 1 e an d iJ column cycle, is of the form dq) d(t) = C iJ + ... + C ij and if we let D.. iJ partition. = (1) {d. J , ... ,d. . ij (t) (6.33) } we have a (k,r) near difference While we do not know if all monocyclic configurations can be so arranged, we may prove th~ following. Theorem 6.5. figuration. Let A be the incidence matrix .2.f i! monocyclic con- Suppose some row cycle of A forms non-zero sections with all the column cycles£!:. A. Then the rows and columns of A may be arranged so that each section of A is a right shift matrix. Proof. We may assume the first row cycle forms non-zero sections with all the column cycles. By permuting only columns we may make all these sections right shift matrices with l's on the main diagonal of each section. For any other row cycle by permuting only the rows of that cycle we may make one of the non-zero sections it forms a right -52shift matrix with l's on the diagonal. Any other section formed by this row cycle must also be a right shift matrix since any left shift matrix would have a 1 on the diagonal because the cycles must be of an odd size, and this would mean a row of the first cycle has inner product greater than 1 with a row of this cycle. The sections formed by the remaining row cycles may be similarly transformed in turn into right shift matrices without changing the shift direction of any previously transformed sections. Thus we can make every section a right shift matrix. The (4,5) near difference pa_r tition in (6.26) leads to a monocyclicconfiguration with incidence matrix ..... A= - 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 - - (6.34) -53Chapter VII Sunnnary In this paper wE have studied various questions about subsets of a finite set S, each of which intersects most of the others in exactly one element and has empty intersection with the remaining few. We began by requiring only that each of these subsets contains three or more elements and has non-empty intersection with at most c-1 of the other subsets, for some fixed positive integer c. We added more restrictions on the subsets and their intersections along the way. Finally, by Chapter VI the number of subsets equals the number of elements of S, each subset has the same size, each element is contained in the same number of subsets, each subset has empty intersection with exactly two other subsets, and the cycles of subsets that arise are all the same size. Along the way we answered several questions most of which gave rise to new problems which remain to be solved. In the least restrictive case which allowed the number of subsets, m, to be different from n, the number elements of S, we showed in Theorem 2.2 that for any fixed c either m <norm is no larger than some positive integer M(c) which depends only on c. However, the exact value of M(c) is not calculated for specific values of c. Next we added the restriction that m = n since except for the low order configurations with m 2._ n this is the extremal case. We proved in Theorem 3.1 that either n 2.. N(c) where N(c) is a positive integer depending only on c, or the incidence matrix A of such a configuration -54has constant line sums and each subset has non~-empty intersections with the same number of other subsets. These configurations are very nearly projective planes except that each line misses a few of the others. From any projective plan of order none can construct such a configuration for c = n - 2 which does not have constant line sums. For c = 2 and c = 3 these are the largest such configurations, leading to the conjecture that N(c) = c 2 + 3c, at least when a projective plane of order c + 2 exists. We then restricted our attention further to those configurations for which A has constant line sums and each set has non-empty intersection with exactly n - 3 of the other subsets. We chosen - 3 since for n - 1 the configurations are the projective planes and for n - 2 they are special symmetric group divisible designs. With n - 3 there is a bit more freedom and configurations of different types can arise. The rows and columns of the incidence matrix can be partitioned into cycles in a natural way. We showed that the intersection of a row cycle and a column cycle, which we called a section, is a right or left shift matrix. We used this to show the number of row cycles of a given size is the same as the number of column cycles of that size. The corol- laries that follow from the fact that the se~tions are shift matrices eliminate many conceivable cycle arrangements for configurations of a given order. However, there are still cycle arrangements, for instance cycles of sizes 3,5, and 15 in a configuration of order 23, which satisfy the corollaries but do not actually occur in any configuration. It is not known whether there are a finite or infinite number of these configurations either in the case where all the cycles are the same size -55or where cycles of different sizes are allowed. Since the structure of each section is determined by the l's in its first row and whether it is a right or left shift matrix, a somewhat more complicated difference partition idea like that used in Chapter VI could be helpful in this area, especially when all the sections have the same shift direction. Besides the difference partition concept for configurations with equal cycle sizes, Chapter VI also showed that the existence of such a configuration implied the existence of a smaller matrix, B, with non-negative integral entries satisfying BB T = (k - A)+ AJ. This implied that solutions to certain Diophantine equations were necessary for the existence of a configuration with equal cycle sizes . There are also many broader problems open for investigation. example, we could require each subset For to intersect most of the other subsets in some fixed number of elements other than 1 and have empty intersection with the remaining subsets. We could also allow a bit more freedom in how a subset intersects the few other subsets it does not intersect in one element. For instance, it might be allowed to inter- sect these sets in zero or two elements. -56·References 1. H. J. Ryser, Subsets of a finite set that intersect each other in at most one element, Journal of Combinatorial Theory A, Vol. 17, No. 1, July 1974, 59-77. 2. D. E. Keenan, D. A. Leonard, On a theorem of Ryser, Journal of Combinatorial Theory A, to appear. 3. R. C. Bose, S. S. Shrikhande, and K. N. Bhattacharya, On the construction of group divisible incomplete block designs, Ann. Math. Statist., 4. Vol. 24, 1953, 167-195. H. J. Ryser, Variants of cyclic difference sets, Proc. Amer. Math. Soc., Vol. 41, No. 1, Nov. 1973, 45-50. 5. A. J. Hoffman, On the polynomial of a graph, Arner. Math. Monthly, Vol. 70, 1963, 30-36. 6. Marshall Hall, H. J. Ryser, Cyclic incidence matrices, Can. Jour. of Math., Vol. III, No. 4, 1951, 495-502.