Maximal Cliques in Graphs Associated with Combinatorial Systems Citation Rands, Bruce Michael Ian (1982) Maximal Cliques in Graphs Associated with Combinatorial Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/e1b1-vd02. https://resolver.caltech.edu/CaltechTHESIS:05172018-100953589 Abstract Maximal cliques in various graphs with combinatorial significance are investigated. The Erdös, Ko, Rado theorem, concerning maximal sets of blocks, pairwise intersecting in s points, is extended to arbitrary t-designs, and a new proof of the theorem is given thereby. The simplest case of this phenomenon is dealt with in detail, namely cliques of size r in the block graphs of Steiner systems S(2,k,v). Following this, the possibility of nonunique geometrisation of such block graphs is considered, and a nonexistence proof in one case is given, when the alternative geometrising cliques are normal. A new Association Scheme is introduced for the 1-factors of the complete graph; its eigenvalues are calcu1ated using the Representation Theory of the Symmetric Group, and various applications are found, concerning maximal cliques in the scheme. 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): Wilson, Richard M. Thesis Committee: Dilworth, Robert P. (chair) Kechris, Alexander S. Ryser, Herbert J. Wales, David B. Wilson, Richard M. Defense Date: 25 May 1982 Funders: Funding Agency Grant Number Bohnenblust Travel Fund UNSPECIFIED Record Number: CaltechTHESIS:05172018-100953589 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:05172018-100953589 DOI: 10.7907/e1b1-vd02 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 10908 Collection: CaltechTHESIS Deposited By: Mel Ray Deposited On: 29 Jun 2018 15:28 Last Modified: 23 Apr 2025 21:48 Thesis Files Preview PDF - Final Version See Usage Policy. 24MB Repository Staff Only: item control page

MAXI!t~ CLIQUES TI~ GRAPHS ASSOCIATED WITH COMBINATORIAL SYSTEMS . Thesis by Bruce Michael Ian Rands In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1982 (Submitted May 25, 1982) ii Acknowledgments Many thanks are due to Richard M. Wilson, my advisor, for suggesting most of the topics of this thesis, providing encouragement to me when trying to prove the results, and always being prepared to listen to anything I had to say. Also for a very informative and topical lecture course in Combinatorics at Caltech 1980-1981. Thanks are also due to Peter J. Cameron of Merton College, Oxford~ where I spent two summers doing much useful work, with financial assistance, in 1980, from the Bohnenblust Travel Fund. He was always ready to answer any questions, and gave freely of his time. Finally, Philippa and Annabel, who have put up with a lot for the . sake of my N~thematics, have been both inspiration and consolation. iii Abstract. Maximal cliques in various graphs with combinatorial significance are investigated. The Erdos, Ko, Ha.do theorem, concerning maximal sets of blocks, pairwise intersecting in s points, is extended to arbitrary t-designs, and a new proof of the theorem is given thereby. The simplest case of this phenomenon is dealt with in detail, namely cliques of size r in the block graphs of Steiner systems S(2,k,v). Following this, the possibility of nonunique geometrisation of such block graphs is considered, and a nonexistence proof in one case is given, when the alternative geometrising cliques are normal. A new Association Scheme is introduced for the 1-factors of the complete graph; its eigenvalues are calcu1ated using the Representation Theory of the Symmetric Group, and various applications are found, concerning maximal cliques in the scheme. iv Contents. Page Introduction Chapter I 1 Association Schemes; Cliques and Designs 3 therein; Further Eigenvalue Techniques; Definitions. Chapter II Maximal Cliques in the Block Graphs of 15 t-designs. Chapter III Cliques of size Chapter IV BG[s:>.(2,k,v)) r in BG[S(2,k,v)]. for general I\ , and 22 55 Nonunique Geometrisation. Chapter V An Association Scheme for the 1-factors 70 of the Complete Graph, and Cliques and Designs therein. References. 95 (1) INTRODUCTION. A clique in a graph is a set of vertices such that any two are adjacent. By a maximal clique, in this thesis, we shall mean a clique which reaches a prescribed bound. Tbs ,bound that we shall be most interested in, in Chapters II, III, and TV is that given by a generalisation to t-designs (due to the author) of the Erdos, Ko, Rado Theorem. The graphs that we shall be conc.erned with in these chapters are the block graphs of. the designs, with the blocks of the design as vertices. They contain certain cliques which correspond to the sets of blocks through a point of the design. The afore-mentioned theorem states that in most cases these are the largest cliques in the block graph. We investigate the possibility of other cliques of the same size, paying particular ,. attention in Chapter III to the simplest case, Steiner systems S(2,k,v). Following this we consider the possibility of nonunique geometrisation of a block graph. This requires the existence of another set of cliques, of the same size as our special cliques, on which can be defined a t-design with the same parameters as the original. We determine a relation between two such sets of geometrising cliques, in the case of 2-designs, and consider in detail an extremal type of clique, which we call a normal clique, and show that an alternative geometrisation by normal cliques of the block graph of a design on the points of the original 2-design gives rise to a symmetric 2-design. Steiner systems can be viewed as maximal cliques in graphs derived from Assoc,ie._tio!l Schemes, the basic theory of which is dealt with in Chapter I. In Chapter V we define an association scheme on the 1-factors (2) of the complete graph on 2n vertices, give a method for determining its eigenvalues, and apply this method for the cases n= 4,5,6. The work relies heavily on the Representation Theory of the Symmetric Group. We again look at various maximal collections of combinatorial significance. 1-factors Viith (3) CHAPTER I. ASSOCIATION SCHEMES; TECHNIQUES; (1) CLIQUES AND DESIGNS THEREIN; Dfili'INITIONS. Association Schemes. An association schem.e on a set _()_ of size the FURTHER EIGENVALUE 2-subsets of v is a partition of fl into . m classes or relations R1, ••••••• , Rm satisfying Sl 9 \ fy (a) x E: (b) x j ye Sl , l x , y 3E Ri (i = 1, ...... ,m) for nonnegative integers p. . k ( i , j , k :: 1, ••• , m) • and To each relation matrix where J 1J we can associate a graph on Ri v. Ai of size J ::= Ao + A1 + • • • • . • • • is the v xv If we let A0 Furthermore we have m L :: Aj Ak= i::: Pijk Ai 0 = I, the identity matrix, we have -+ Am , matrix of all _(l with adjacency 1 1 s. (4) v1here the So the with one or more subscripts zero are suitably defined. P·1J·k's A. 1 s J. span an associative and commutative algebra Q , known as the Bose Mesner algebra of the scheme. Let V be the v-dimensional vector space over the complex numbers on which the matrices A. can be said to act. 1 V ::: V0 (f) orthogonal decomposition of the Ei Then th ere exists an v1 cf) ••..•. (t) Vm A.'s, which are simultaneously diagonalisable) J. denotes the matrix of the orthogonal projection It is customary to take V0 such that if then V ~Vi' = span f (1,1, ...... ,1).,.3 . The V.J. 's are known as the eigenspaces of the algebra, and (2) (the eigenspaces dim V.1 =I A.L • , say. 1 Eigenvalues of the scheme, and Delsarte 1 s inequalities. We have for scalars Pj(k) which are known as the eigenvalues of the scheme. It is not difficult to show that the Pj (k) 1 s, together _with the ,1-A 1' s determine all the parameters of the scheme. Delsarte (7) develops conditions on the distribution vector of a subset of elements of the scheme in terms of the eigenvalues. subset Y sQ, vector with its distribution vector a is an m+ 1 Given a dimensional (5) a.1 -- 1 i \Y\ = 1 to m. Delsarte 1 s inequalities state that m z. for i ~ j .:: 0 0 to m, and so a knowledge of the eigenvalues restricts the possible subsets of the scheme. Let _ ~y be the characteristic vector of Y. Then the inequalities are equivalent to the fact that m since (5) The Johnson and Hamming Schemes. The Johnson scheme is defined on of a v-set. There are k ~(v), the set of all k-subsets nontrivial relations, (as long as v ~ 2k4- l), depending on the intersection of the two sets, i.e. if and only if These schemes provide a general setting for the theory of statistical designs, and set intersection problems. The Hamming scheme is defined on v GF.( q) , the set of all vectors (6) C.L t-L in a v-<limensional vector space over a finite field. There A v nontrivial relations, depending on the number of nonzero entries in the difference !_ 1 - ~ , 4 for two vectors in the space. These schemes are of use in the theory of error-correcting codes. The eigenvalues of the Johnson scheme are given by i p,I (j) = L u:o = E; (j), an Eberlein polynomial. For the Hamming _scheme . we have j- P, (j) = u (-q) (q - 1) 2. u:: i , 0 i /Ai. = (q - 1) =Ye. (4) A simple application of eigenvalue methods. Let us suppOSE? that we have a family (where v ~2k + 1), Q_ of k-subsets of a v-set, which pairwise intersect in at least one point. Then this is a coclique in the graph corresponding to empty intersection. We have the following bound due to Hoffman (18) coclique in a regular graph, namely on the size ~ of a (7) where ,.J < -v A. V\. -- , d -i\ v is the number of vertices, d is the valency, /\ is the minimum eigenvalue of the adjacency matrix. By examining the eigenvalues /\ :: Pk(j) : (-1) ( is the smallest eigenvalue of v - cf the graph, we find k - 1) k - 1 Ak. ::. This is the simplest case of the theorem of Erdos, Ko, and Rado (5) 1) . v ( k - 1 (12). The code-clique theorem. A subset Y of an respect to relations m-class association scheme is a clique with ·-:1 fRi ~. i ~ N3 for some subset N of [ 1, •••• , mj , if its distribution vector satisfies for all if N, It is a code with respect to these relations if at :: 0 for all i l- N. i I o. (8) Let Y be a code with respect to i E: N ~ , [ ~ a clique with respect to the same relations. and Z be Then For a proof see Delsarte (7). (6) t-designs in the Johnson scheme. A t-( v, k ,'A) set of size v, design is an ordered pair·.~ (X,~ ) , <J3 and (}:;, • Consider a fJ t~v), X is a (blocks) of X X is contained in exactly I\ is a family of with the property that any t-subset of of the blocks of where k-subsets r To avoid degenerate cases, it is assumed that . (~) by (~) matrix with rows indexed by and columns indexed by rfJk(v), with if t c. B, if not. ¢y is the characteristic vector of the blocks of a t-design, Then if ' where j_ is the (~) column vector of all ones. (9) i.e o, t) v ( k - t j_ / where is the l ~) column vector of all ones. It can be shown ~ - (7), that the row space of Hence, if Nl:_,IC V0 ® V1 @ ••. {!)Ve. is ~y is the characteristic vector of a t-design, (7) The- ::. degree of a subset of cPK(v). This is defined to be one less than the number of nonzero entries in the distribution vector of t he subset. due to Ray-Chaudhuri and Wilson Theorem: If a subset Y of Theorem: The number of blocks, We have the following theorems (25). rfJK(v) J has degree <J3/ , . of a d, then 2s-design satisfies Proofs of these can be found in (7). Finally, we have the following; Theorem: Suppose we have a t-design Y of degree Then the restriction of the Johnson scheme to scheme with s classes. See Cameron and Van Lint (5). s, with t ~ 2&~·- 2. Y is an association (10) (8) Interlacing Theorems. (15) gives a full account of the method In his thesis, W.Haemers of interlacing for the eigenvalues of a square matrix and a square submatrix, and many applications in the theory of graphs and combinatorial structures. We give here one of his fUndamental theorems, which we shall make use.~ of in Chapter III. Definition: Suppose that numbers, of size n and A and B m, m ~ n. respectively, with A n-m+i (A) for all If to B are said to interlace those of A. k ~ o, If there exists an integer and square matrices over the complex i = 1 /\ i (A) ?- Ai (B) >,., · then the eigenvalues of a~e A n-mti (A): A i (B) for i for i :: k + 1 : 1 to k~ m, m, such that k, to m, then the interlacing is said to be tight. Theorem: (where Let S be a complex S~ is the complex conjugate transpose of Hermitian matrix of size (i) n. S * S :: Im , Let A be a n x m matrix such that Define the eigenvalues of ~ B =- S A S• S). Th en, B interlace those of A. (11) (ii) i €. f 1, ••••• ,m1 , eigenvalue If /\ (B.) E. S A (A), A (A) ( for some n-m+i J then there exists an eigenvector y_ of B with 2. i /\ (B), such that S y i i is an eigenvector of A with the:·· same eigenvalue. for all i e.fl, •••• ,k5, /\ . ( B) , ]. th en -1 is an eigenvector for is an eigenvector of S v -i (iv) v and Ai (A) ::: Ai (B) . k t- ~l, ••..• ,mj, (iii) If for some B with value A with eigenvalue /t (B) i If the interlacing is tight, then S B =A S • T o] . For our purposes, (9) Other Definitions. A Steiner system we write a t-(v,k,~) s(t,k,v) is a t-·(v,k,l) design as an Sl\.(t,k,v). A symmetric block design is a b ~ v. of blocks b~ v, By 2-(v,k, '/\) When A>l, design in which the number the second theorem in section (7) of this _Chapter, which is Fisher's inequality. A pairwise balanced design is a pair of size v and (j3 . (X,<'.8), <J3 is a set of subsets of X, such that any two points of of design. where X is a set (of no prescribed size), X are contained in exactly one element (12) The block graph of an S(2,k,v), written BG(s(2,k,v)J , or BG when it is known which Steiner system we are talking about, bas as vertex set the b blocks of the Steiner system, and as edge set the pairs of incident blocks. Block graphs can be defined for more general designs. A partial geometry and a strongly regular graph are as defined in Bose (1). A strongly regular graph can also be regarded as a association scheme. 2 class (15) CHAPTER II. MAXIMAL CLIQUES IN THE BLOCK GRAPHS OF (1) extension of the Erdos, Ko, Rado theorem to An (26) In Theorem: Let ~ represent the set of blocks of a following property: for all t-designs. the following theorem is proved: 0 < s < t ~ k, Given t-DESIGNS. A,B € Q then there exists a function suppose there is a set , t-(v,k,A) design. f(k,t,s) with the Q f (JS of blocks such tba t then if v ~ f(k,t,s), \ Q_} ~ b s ~ the number of blocks through Furthermore, if v > f(k,t,s), s then the ~ only families of blocks reaching this bound are those consisting of all blocks through some s s points. If s <. t - 1, then f(k,t,s)~ s .+(~) (k - s + l)(k - s). If s =- t - 1, then f(k, It is well known that for any through pain ts. X, points of t,s)~ s + (k - s) (~/ • s ~ t, the number of blocks, is independent of the choice of these points, and b5 bs , /(kt - SS) =A ( tV- ~)i _ '/ (14) Extensive use is made of the fact that Let tf> ~ v) denote the set of all may be regarded as a k-(v,k,l) design. theorem due to Erdos, Ko , and Ra.do, Theorem: o' < s ~ k ~ v, Given k-subsets of a v-set. Then it So the theorem has the following (12), as an immediate corollary: then there exists a function with the following property: suppose there is a set of a v-set such that for all A, B €-Q, \ A (\ B \ ~ s; g(k,s) Q. of k-subsets then if v~g(k,s), , the number of k-subsets containing an s-subset. Frankl (15) has shown that if s ~15, then, g(k,s) = (k - s +- 1) (s 4- 1) + s, and conjectures that this holds for all s. Proof of the theorem: Let theorem. Cl be a· family of blocks satisfying the conditions of the Let t be the set of s-subsets which are at the intersection ct. Let np be the number of blocks of Cl of the family containing the s-subset p . Let /Cll= w. of at least two blocks of e (15) Count (p,B) such that p€ l , > np~w (~) ~ Count (p,B,A) such that p ~ B l:: Q , p ~ B (\ A' with to obtain, . pt-£ ' z_ n .(n - 1) p~e Now if w(w -1). p a is not the set of all blocks through an s-subset, then , for each p E So if and at least e' A~ other block B. p A' B e Q Cl Q. , there is some block BE which contains contains at least p, is the maximum · number of blocks of d s points of w{w - 1) w- l If d B, then n p~ d. 03 with pf B. lmy s which contain Hence, ~ {d - 1) ~ n p ~ {d - l)w (~) , ~ (d - 1) ( ~) (~) ~ b s ' and so we are done. The following lemma gives an upper bound for d. points of p (16) Lemma: Let Let d be the number of blocks containing of B. Then or p be an s-subset, and B a (i) if s ~ t/2 (ii) if t/2 < s <. t - 1 v~k and block not containing p and at least 2. s p. points + 2t, v ~ s +(~) (k - s), and then (iii) if s :. t - 1, then Proof of of p, (i): for some Take an s-subset p and a block B containing r points r < s. s-r 1(- s s-r f Let dr of B. be the number of blocks containing p and at least s points Then since there are of B n p, r) k ( s - r s-subsets o.f B which contain all points and these, together with the remaining each determine a family of b 2s-r s - r points of blocks with tbe required property. p, (17) These families have in their union all such blocks. 8 r+1/er Clearly, - (s - r){v - 2s + l)/(k .- r) (k - 2s + r + 1) ) (v - ·2t)/k 2 • 'L So if v~ k d r ~e s-l =- and so Hence then + 2t, d e r+l > er for all I( v _ s _ 1) k _ s _ 1) t - s - 1 A (k - s -t- 1) ( t - s - 1 . is bounded as required. Proof of (ii) Let maximum number of blocks containing and (iii): So if j ~ t, then c~ = b-t.J ' ·J but, if j t, then cj ~ )\. • Then with r<s - 1, ~ as in the proof of case ~ ~ ( k - r) s - r j points of X. (i), ~s-r = 8r ' -~ So, if r < 2s - t, then ~·;'. ~ 1{: =~)~(~)'A; if r ~ 2s - t, then ~ ~?i.(k -2t 2s- <t-2s t) if r > 2s - t, then dr~ A (k-r)(v s - r t - 2s + - 2s + It is clear, using the same argument a s in (i), that, 2s + r) ~)/(~ - 2s+ r . (18) d ~ max dr ~ max ( e 0 as long as v ~ k s < t - 1, If 2. then s = t - 1, If es _ 1 ) + 2t. v~ t +(~) k, So if , then d ~max then d (). (~) , d .$ ~ max A (v - t)/k ) • .?\ (k - s - 1) b s + 1 • ( A ( ~) , A (k - t) ) ;: ( ~) A. So ends the proof of the lemma. We want In cases (i) i.e. (!) or v ·- · and (ii), this requires (k - s +- l)(k - s) ~ s ~ (k - s) (k - s -+ l) ( ~) , as in the statement of ...,.. the theorem. In case (iii) ~ (v - s), this requires (19) 2 /\ ( ~) ~ 'A (v - t + l)/(k - t + 1) v ~ s 4- (k - s) ( ks) 2 or We have strict inequality in [Cl{~ bs, when v satisfies these conditions, and Cl_does not consist of all blocks containing s points, so the other conclusions of the theorem hold. (2) Corollary: If ~ v ~k , then at-design, with t.:;:-.2, has disjoint -· . blo·~s ;~ Proof: We need only consider design intersect. Then 2-designs. Suppose any two blocks of the Q3 , the set of blocks of the design, satisfies the bound in the proof of the previous theorem, given by VThere s = 1. Hence If v pk '2- , this is impossible. We provide another proof of this fact in Chapter rv. (3) @ a paper of Deza, Erdos, and Frankl. In this paper (11), the authors prove a number of theorems which extend the ideas of the Erdos, Ko, Rado Theorem. They define a (v,M,k)-system (20) Q C (Pk (v), Let such that for any two distinct M = ~ mlt m2 , •••••• , mr) A,B ~Q , J A " B1 ~ M. m1 < m2.<········< m,.<k. ' Then they prove,among other things, the following; If ()__ is a Theorem: (v,M,k)-system, v ~ g(k,s) for all s < k, DS B for all r and \ Q {~ c(k)TJ (v - mi )/(k - mi) . i =2. (i) tpere exists an B ~ Q_ D of X such that • (m~ - m I (m~ - m,) I /! ~(a/. (ii) (iii) m,-subset then 1) (v - m,)/(k - mJ I (m,.. - m,,._ 1) Remarks on this theorem and its applicability to designs! (a) The condition that For consider the tight v is large compaired to 4-<lesign 8(4,7,25). any two distinct blocks intersect in 1 theorem, we get I 1~ (B 22. 20/6. 4 or k is very necessary. This is unique, 5 points. (19), and If we apply the < 20, whereas the design has 255 blocks. (b) The authors remark that equality in (iii) is realizable by the family of hyperplanes of any perfect matroid design. (c) For the case JMj ~ 2, the designs with this property are called (21) quasi-symmetric and are dealt with in Chapter DI. v~k '2... for these designs. However, it is also shown that the divisibility conditions for the intersectlon numbers (d) (as in Ia..1~u;1) As was stated in Chapter I, In most cases : >'(iii) It is shown there that ' (ii) ) hold. for any (v,M,k)-system. is stronger than this, but it must be said again that this only holds for large v. (22) CHAPTER III. CLIQUES OF SIZE r (1) BGls(2,k,vil. IN Cliques have size at most To an S(2,k,v) for all '2.. v>k -k+l. we ascribe two more parameters , namely b :- v(v - l~ k(k - 1 where r r:-v-1 ' ' k - 1 is the number of blocks of the design, and b r . is the number of blocks through each point of the design. We make use of the fact that · graph, since S(2·, k, v) is a partial geometry. k(r - 1), (r - 2) + (k - 1{, and so its adjacency matrix, AL + Therefore A BG[S (2 ,k, v )] A, ( 2k - r + 1) A - is a strongly regular BG bas parameters satisfies k (r - k - 1) I :: ka. J has eigenvalues k(r - 1) once, r - k - 1 v - 1 times, -k b - v times. (23) Now we look at the v/ k 'Z.. - k + l, 5--dimensional algebra generated by b > v). A, (since The second nontrivial idempotent of the algbra, is given by E 2. + (J - A - I) ( - Ai. - 1) I + A i\JJ =[ v - d - 1 }:· using the notation of Chapter I. Let BG. ~ be the characteristic vector of a clique of size Then: the condition w ~ ¢'Ea_~ ~ 0 w in implies ~ w(w - 1) ~ 0 or d w,$l+d -'i\'L which in our case gives w ~ r. If equality holds, then - A E2 cP =0, and so L + ( A - I) (k - 1) 4=0' r - 1 -k ( r - 1) + (!£ - 1) J - k A p= ( r - k - 1) ~ + k ..i = (r - 1) rp + k (..i - which implies that any vertex of adjacent to ey..actly of Delsarte (7) k p) B ' not in the clique of size vertices of the clique. r is And su, in the terminology this is a completely regular clique. (24) There are numerous ways of proving this result. Elementary counting methods have been used by Bose (1), and Neumaier (24); the latter would call this a regular clique of size r and nexus k, and shovTS that if an edge regular graph contains a regular clique of a given size and nexus then any other regular clique must have the same size and nexus. This is of interest in our study because it implies that the block graph of a Steiner system S(2,k,v) can only be the block graph of another Steiner system if it has the same parameters. One can also use the interlacing method of Haemers (15) to prove this result but it is very similar to the association scheme method. (2) The pairwise balanced design on C. We find the best way to look at this problem is to dualise and to consider the partial geometry on b vertices, with such that any two lines meet at a unique vertex. graph of this partial geometry. to the set of r A clique BG v lines of size r, is then the point C of size r , not corresponding blocks through a point, is then a . '~' set of r : . vertices of the geometry such that any two lie on some line of the geometry, and in fact the restrictions of the lines to the r vertices of pairwise balanced design, except for the fact that this C form a p.b.d. may have repeated blocks of size one. This p.b.d. has the property that for any two of its blocks, if they have combined size greater than not. k, they must meet. For suppose Then the lines of the partial geometry to which these correspond meet at some vertex outside the clique. But then this vertex is adjacent (25) to more than k vertices of the clique contradicting (1). We shall make repeated use of this property later in this chapter. We note ;,~h§l-f fo:r: any line L of the Jcn1)~k. Otherwise a vertex vertices of C. p. g. , ~ if f L , then x € L' C is adjacent to more than This can also be seen in the following manner. c, B be a block in a clique and k Let a point of the design not on B. p f So if most C is not the set of blocks through a point k of the blocks through p , C contains at p because there are only k blocks through p · -~pich;·,intersect. .B • .. .· -- ·- .·- ' ·. -~-- . . ~- We shall call a line of the partial geometry an to a certain clique clique. Let C, of size r , i-line ~dtb respect if it contains i vertices of the i ~ k. If the clique does not correspond to a_;_line, then • be the number of i-lines with respect to c. n• As can be done for any equations for the :z_ p.b.d. , we form -~he following system of n; 1 s. I(. ic 0 D• =v counting lines of the in·I = rk counting (x,L) , x € c, I p.g. I( ® .L 1::- 0 x ~ L. K L ( i - l)inj :: i"=o r(r -1) counting (x,, x2.., L), X 1 , x2 E c l"I 1 (26) We shall apply these equations to particular cases. We may .rewrite these equations in terms of variables Let h be the number of lines which contain at least one vertex of 2_ l l = h, ;f_ rk, C. l: !L..f\C..l>O L ~ : ~ (~ - 1) :: r(r - 1) . These equations imply 2_ (~ and so r + k k it rk h - '1. r + k - 1 , is a minimum when h r + k - 1 k intersects is a constant for each line L which C. Such a clique C , where any point covered by the r blocks ofi: C lies in a constant number of these blocks, we shall call a normal clique. We have shown that ·the blocks of a normal clique cover the minimum number of points of the design. upper bound for Let n It would also be nice to be able to find an h , the number of points covered by blocks of be the least integer greater than (r t k - l)/k. C. Then if (27) C is not normal, some point lies on at least some line L of the p.g. intersects n C in at least But then any vertex x E L 'C lies on at most intersecting C, and so on at least n - 1 C. There are at least and h ::=; v - (n - 1) (r - n) and the p.b.d. on r - n h~v So 0 (n - l)(r - n) with equality if and only if r = n - n + 1, 2. n. c, m blocks of ,_ r= m -m-4-1, with equality if is a projective plane of order h vertices. other lines :,'.~ , : n ~ C is a projective plane of order - (m - l)(r - m), This bound for k - n n i.e. lines which do not intersect such vertices. More generally, if some point lies on c, blocks of rn~~ > and the p.b.d. m. is not entirely satisfactory but we will see an example of a design later where both the upper and lower bounds are met. (5) If r > k'2- - k-+- 1, BG(s(2,k,vU Let are those corresponding to of r r in blocks through a point. C be a clique which is not a line of the partial geometry; then any vertex through then the only cliques of size x x of C lies on exactly contains at most k vertices of k lines, C. and any line So, since any vertex C lies on a line through x, Ic1 ~ k(k - 1) + i. This result was known to Bruck (2) and Bose (1), and is also a special case of a theorem of Deza (10). (28) (4) The case where IC /"I L / Suppose we have a line clique C of size covered by r in =k. of the partial geometry intersecting a L k vertices, Consider the subgraph of of C '1 a point of S(2,k,v) blocks of the clique). k vertices of (i.e. L ....._ C and the BG[S(2,k,v)] r - k is already adjacent to consisting of the vertices of k Now any vertex C-..... L. vertices of L r - k 1 ~ C ). (namely 80 it cannot be adjacent to any vertices of 1 ........ c~ In other words CAL is a pair of disjoint cliques of size r - k, with no edges between ·. _them. Label the vertices of of and t he next C "-1 r - k are those of is an eigenvector of the subgraph But r - k - 1 Ct:::.. L, (15), the interlacing theorem of Haemers g' 1· ' c· . Then u -- ( .1.Lf'-lc. i -i ,.. ) ' .>L . -1( - r - k - 1. with eigenvalue is the second eigenvalue of _ BG, this eigenvalue with multiplicity two. that r - k- are vertices so that the first BG whereas C o. L Hence we can use part (see Chapter I), has - (ii) of which implies = U.r.-1(.,-lr-><-, Ql,,--24°'-oc:)) is an eigenvector of BG with eigenvalue r - k - 1. Hence 2(r - k) L a 1J, j::r-k+l i.e. for any vertex adjacent to to x. x x~ C 61, 2 (r - k) + 1 ~ i Sb. the number of vertices in is equal to the number of vertices in 1' C (Note that this holds trivially for the vertices in C ,1 adjacent C .fl 1~ • (29) Let ai vertices of be the number of vertices not in L '- C and i of C "'-...L. = b - 2r .,.. k, C u L, adjacent to i Then (r - k)(k - l)(r -1), counting (x,y), x.: L .... C y ~ BG -.... (L '-' C), 2:.:-i(i - l)ai : (r - k)(r - k -l)(k -1) counting x,y ~ L - These equations will be applied in c, x ,..., y, (x,y,z) z "'-X,y. (11). It is possible to obtain similar equations when by making use of the fact that the complement of IC '1 L \: m < k, CAL is bipartite. We have never found a use for them, however. (5) The case An r =k. S(2,k,k!';- k + 1) point-block incidence matrix N NT and so is a projective plane of order The N of a projective plane satisfies = (k - 1) I + and J N is a nonsingular matrix of size A well known result of eyser matrix manipulation, k - 1. =: kJ (@) v. (see Hall (16) ) , that equations NJ (@) imply shO\'IS, by simple (30) 1 N N : (k - 1) I + J 1 and N J kJ c So any two blocks of a projective plane meet in a point. is the complete graph on From now on we exclude the case r ; k k ~ - k + 1 Hence vertices. from our investigations, as the block graph gives no information about the des i gn. ( 6) k The case r :::: k + 1. b :: k(k + 1). Take a point p and a block blocks through p which intersect B and so one that does not. I k'l.. blocks which intersect in a parallel class of one of them., k "2 ~ S(2,k,k ), k. is the complete There are kf(+- 1 (k + 1)-partite cliques of size r = k + 1, k 2.. of them correspond to · k~ 1 From this description it is easy to see how to an affine plane of order a projective plane, by adding the parallel classes, f. B • Hence any block B lie_s consisting of a block from each class; blocks through a point. B= So blocks such that any point lies in exactly Hence .:.. _~BG S(2 1 k,k ) graph with parts of size extend an Pf B ; t hen there are P4 B lies on a unique block B such that B' n every point There are such that B ) k ~1 k, to an '2. S(2,k,k +k+-1), more points which correspond to and one more block, the block at infinity, :_-, - __, containing these points. (a) k ~ 3, r:: 4, v:. 9, b ': 12. This is the unique affine plane of order of the form 3. Its. block graph has cliques (51) 9 of this type, 72 of this type, none of this type, because, if there were, let . B be the block through x,y. Then B and they do exist, because all lines meet the line at infinity, 1 00 , intersects all four blocks of the clique, a contradiction. (b) k: 4, r : 5, v::; 16, b:: 20. The unique affine plane of order 4. Now it is possible that there are cliques of the form in distinct points (since they already meet each other), in the extension PG(2,4). Now we have a set of six lines in PG(2,4) lies in 0 or 2 of them. sa.ch that any point This is the dual of an oval in PG(2,4) and it is well known that these exist, (see, for example, Biggs and White (0) ). In fact it is known that there are three orbits of size 56 168 of them and they divide into under the action of the group PSL(3,4). The (32) ovals in a given orbit intersect in transitivity of PSL(3,4) 0 or 16 points, and by the each point lies in dual-ovals containing one further line in common. L 00 16 R~turning pairwise intersect in one other point. have 2 of these ovals which to the dual set-up we such that any two of them have So in our block graph we have 16 pairwise intersecting in a vertex of the graph. Since 5-cliques PSL(3,4) is doubly transitive on the lines of PG(2,4), and so transitive on the lines, not is at the intersection of two of our L00 , any block of dual-ovals. AG(2,4) Hence we have another geometrisation of the block graph. We notice that the sixteen cliques are normal cliques in the sense of section (2). Now the cover 10 Any line 5 blocks in the clique corresponding to the dual-oval points of of AG(2,4), PG(2,4) must go through 3 and so there are six remaining points. must meet all the lines of the dual-oval, and so of the 15 points covered by it in it contains two of the remaining in Loe points. So these six points form Lo0 , and in the same orbit under PSL(5,4). or 2 0 points. Suppose and from each other. of them o, So they intersect 02. are ovals disjoint from and There ·are six lines exterior to 0I , one , and five others, each of which contain exactly 2 of Loci the remaining meets 4 points (S). that L, LI () s and L2" s. This implies that Hence the Hence In this way we have 16 ovals in PG(2,4), disjoint an oval again. from 6 PG(2,4). Consider three of them L.z, and Lz. meets L3 l'l. s are 2-subsets of 16 L~ s LI,-- L2, L~, in points • inside Then which are both disjoint from IL I l"I Ll} :::- 2, a conflict. ovals disjoint from 0 2. • such Lo0 form a (16,6,2) So /o I " o~) = 2. symmetric design. (33) Hence their complements in AG(2,4) form a (16,10,6) design. This example illustrates a number of points we shall develop in Chapter IV. ~·~ ·. one It is interesting to wonder whether for even can produce the same sort of set-up. We shall show in Chapter IV 4t~ dual-ovals which geometrise that if it is possible to find a set of the block graph of AG(2,2t), then there exists a (4t\ 2t2. + t, t,,-t t) symmetric design associated with this construction. be obtained from Hadamard matrices (7) k, larger than The case Let Such designs can (see Hall(l6) ). r=k 2.. - k + l . and S(2,k,v) parameters as the points and lines of projective 3-space. (a) n ; k - 1, then v z:: nl+ nl.+ n + 1 .Any clique of size r in BG, bas the same not consisting of r blocks through a point, is a subplane. We have equality in the bound in (3) of the partial geometry intersects p.b.d. on C in C has replication number k which implies that any line 0 or k vertices. and block size k So the and so is a projective plane. (b) cliques corresponding to subplanes If B(:L has then the Steiner system is the set of points and lines of so n PG(3,n) and must be a prime power. (i) Any two subplanes have at at most one block in common. If they have more than one, they (as cliques in BG) have an edge x,y in common and this lies on one of the lines L of BG. has Let c 2.. 'A = (r - 2) ~ (k - 1) '2. 2 (k - 1) + k - 2. But and BG D represent (34) the subplanes. Ignoring the vertices of are already joined to the same le n LI ~ k). c or L. x D for the moment, and y '- 2 (k - 1) + k - 2 vertices, (since Hence they cannot both be adjacent to any vertices not in Hence k 2- - k + 1 ~ 2k - 2, or (k - 2) (k - 1) .s -1, clearly impossible. (ii) Any edge lies in a unique subplane. Any subplane contains edges, (n':l...r n + l)(n2...+ l)(n + l)(n-z.~ n)/2 BG has n~+n"l..~n+l There (n 'l..4- n + 1) (n'2..... r\)/2 edges. subplanes with no edge in common, hence the resuJ,t. So we have another geometrisation of the block graph. (iii) Any triangle consisting of three blocks intersecting, but, not at a fixed point, lies in a unique subplane. AllY: subplane contains BG has n'2..(n't.+- ~ : ~ l)(n + l)n/6 (n,_-+- n + 1) (n'2.+ 1) (n "l+nl (n + l)n/6 ~\ '. . such trian_g1:_e s, such triangles. No triangle lies in more than one subplane, hence the result. Now take and suppose B1 , B2., B~ forming a triangle·, viz. B intersects B1 and B,. Then B B1 BL forms another (35) triangle, and so they lie in some clique corresponding to a subplane say. B 1 B2 B3 lie in the clique Let we have C .:: . D;·7' and so C. B intersects Since B3 • Tb ere fore the blocks of our Steiner system satisfy the Pasch axiom and we have projective over GF(n) (since D, 3-space 5-space is necessarily Desarguesian). We have shown that the only BG of a design with these parameters which has nonunique geometrisation is that of the ~points and lines of projective 5-space. Moreover, there is a symmetric design between the points and planes of the design with parameters (n 1 +ni.+n+ 1, n'2.+n4-l, n+l), and the cliques corresponding to subplanes are normal cliques. (e) Lorimer~ . construction. Lorimer (21) has given a method of constructing an · S(2,n +l,n 1+n~-+n +l) which is resolvable, contains at least n2. .+ n + 1 whenever there is a projective plane of order n. subplanes, and exists His method could conceivably give a large number of such designs for each n > 2 and will also be of use to us later because of a construction of De~niston (8), and so we will give it in some detail. Let '1T be a plane of order be a set of n ~ 1 n. For each line permutations of the points of L of .,,- , let L Gr, such that; Gr, ' (1) 1 € (2) Gr, is sharply transitive on the points of L. This requires, in effect, the existence of a Latin square of order and the cyclic group of order n +1 is one possibility. n ~ 1, (36) assuming the identity in each are distinct. lxl = 1 + n(n'2.+ n +-1). So Blocks en GL is the same, and all other permutations X are of two types, L ~It xf. L, for (B) call the block determined by which we and x L. (n2.. + n + 1) (ni.+ 1). So the number of blocks is It is not difficult X. to check that these give a design with the required parameters on All blocks have size lie on some block. n + 1, so we only have to check that any two po~nts Truce f ~ GL, If M"f L, Let N be the line through let x c,,. g 6 M-= L then If be the point of intersection of f- I (x) and g-'(x). L and Then f,g~GL. M in Tr. f ,g ~ Bx L' ' To prove the resolvability of the design we need to define a loop structure on X. and define (fg) (x())::: f(g(x 0 )) with 1 First we do this for each for L. Truce a particular f ,g € L. This mruces 6~ L x GL a loop as the identity. Now take f ~ Gu the line of T\ through g ~ G1'1, f (x) j L. M and Let g -r (x). (fg) (g- 1 (x)) = f (x), l lx = M n L and Define so g -..,fg and g~gf g ~fg SUppose g,, g 2 L t'\ M i. :: ~ xi ~ ~ be f g by fg e GN. To show that our definition gives a loop on that the maps N X, are bijections. we need to show We do the first. is certainly a bijection on GL. X-.... GL and for i :o 1, 2. Since fg 1 :: fg2. , these lines must be (37) the same, say N • xl: x 2 : x say. But N meets L f (x,) ~ f (x~) at and so So we have the following picture. N But fg,.,.. fg~ = h h(g~l(J-F))-:: h(g;'(x)) = f(x) and ~ g:' (x) : g~ 1 (x) since G N is a loop, The other proof is similar. So ~ gz. ~ g 1 • is a loop. X Now we · consider the left cosets of the subloops a line of Tr , and Put x = f(y). Let g €. GL, f ~ X ' G L. and let N be the line through fg ~ GN is such that So Therefore -I (f g ) fg(g- 1 (y)) :: f(y) ( x ) :: g -I fg ~ B::ic_, L. Conversely let h ~ Bx L" ) = x. (y ) E L • So fGL ~ B ~... l . Then M :f. L, f E GM , Say 1 u :. h- (x) t: L. GL. x and Let L M () L .: 1 g- (y) • be lyj . (38) L Let gt: Gl be such that So h ::: f g E fG L. • g(u) ~ y. Then Therefore GL .is a partition of the elements Now the collection of left cosets of of X, or Bx~ and so the corresponding blocks form a spread. x~1T X, x. contain Then if P 1 and so for all f ,g E: GL, h E. Gl , Let and every permutation in X contains two points from a block it contains the whole block, For suppose P is a plane isomorphic to and f, g ~ P • f, g do not fix so x , x~ L, h ~ P. x E L and M. h _, (x) E. N so B.:x. 1'.l ~ P • =) G~ X contains subplanes isomorphic to 1T . , and P 5= X which does not fix of Ea.ch block lies in one such spread, and so the design is resolvable. , Finally we show that Let h(g- 1 (y)) ... h(u):: x = f(y). f,g x1 e B..:ir::. . "'1> , f ,g € P, N, but for all hE- B~,,N ' ~ The isomorphism This implies that ~:II~ PS X X contains is such that cp(y)(y) = x. n2 + n ~ 1 planes isomorphic to Tl , but it may contain more. The simplest case of this construction is for the plane of order There is only one loop of three elements, and this gives rise to 2. PG(S,2). (59) The next is that which arises from the plane of order four permutations loop GL , v 4 =~l, 5. If we use the (12)(34), (13)(24), (14)(25)f we do not get pr-oj ecti ve 5-space; by the following base blocks (mod 15), for each its blocks are generated (c.f. Denniston (8) ). B3 Bio Ds Db c«i c~ B2 Bs D1 D12 CL C 2. B 4 Bb C7 DI\ c12. cs D1 B7 D10 D2. B 11 C ~ D1 B1 BI B 10 It is invariant under the nonabelian group of order 39 59 and contains subplanes, images, under the group, of the points A B0 C0 D0 B<c. c, Db Bi' Ce (one element of the group, of order 3, B~ Ds- Cc; Dci • multiplies suffices by 5) • . We will make further use of this design. One might wonder what would happen if some V'+ loop structure, and some the (8) r =- k The case '2- - k. Suppose there is a set of k~- k the same point, and pairwise intersecting. k - 1 points which are covered by covered by k- 1 . blocks of (k - 1)-points. were given the C't (cyclic group) structure. We show that there are no cliques of size in ·BG. GL ts k '4 k -k, blocks (C) except the lines not all through Then each block of blocks of C, and one point But then there must be C. However no two can lie on a block of some block Bf C containing at least two adjacent to 2k - 2 blocks of C . .And C . k of these So there is (k - 1)-points. 2k - 2 > k C contains unless Then B is k: 2. (40) (9) k = 3. Steiner systems with We are only concerned with the cases r =3,4,6,7. Our previous analysis has dealt with all these, so we know all about cliques of size (10) r in " BG S(2,3,v) Steiner systems with k = 4. We have six cases where we have to look, = 4, 5, 8, 9, 12, 13, v :: 13, 16, 25, 28, 37, 40, r and we only have to consider the two new cases r • 8, and r ~ 9. We make repeated use of the special property of the p.b.d. described in (2). vertices of BG which are adjacent to more than C (supplying our contradictions) by x. Lines through C are shown as smooth lines, where possible, and vertices as • • r -= 8, v = 25. Case n.., r 2. C To save much explanation we make extensive use of diagrams and indicate vertices of k on (41) These constructions are the only possible with so ll4:: 4-lines, o. Hence BG[S(2,4,25)] r c: 9, v = 28. n'+ has no other cliques of size 8. =5 n~ s:- 1 so the n* c o, implies that all vertices li e on four p.b.d. on C is AG (2, 5 ), 3-lines, and but t his has disjoint blocks of ( 42) size 3. So BG[S(2,~ 1 28)] (11) Steiner systems with has no other cliques of size 9. k .:: 5. We have eight cases of interest: r - 5, 6, 10, 11, 15, 16, 20, 21, y .:: 21, 25, 41, 45, 61, 65, 81, 85, and need only consider the four new cases, (a) r= 10 ! Take a r =10,11,15,16. v= 41. Then there are only six 3-line. 2-lines disjoint from it inside the clique, whereas there would have to be seven. 1-lines and they already meet inside n't Let and x,' XL' X3 Z I' Zz. :: There are only .two C. 2, be the remaining vertices on be the remaining vertices on Without loss of generality we have lines L the 5-line. Let Yr , Yz.. M, N (4-lines) respectively. 1x,' [ XL, Zz.' Yi? z, ' Y, S ' ' (45) ~ x.11 ~, y "L ~ , intersect [x~, z 1 , Y, 1 N and does so in for the linecontaining can intersect. ns = 1, n<t :: o, x1y1 , z1 , (since the line containing Xi~ or z2 ). must But now the same applies but there is no point of N where it... (44) n"t- :: 3, first case, Any line through z through each of L (") M, must intersect L ~ N, will have four vertices on it. n&+ ::: L, M, and M ~ N, N. There is one line and on e other. But this one We have already dealt with the case n+ = 4. 5, second case, Now any other line must intersect each of lines, not through z, are 3-lines. L, M, and N. So all other z, the restriction If we delete to the nine remaining vertices of the clique must be has disjoint AG(2,3). 5-lines. At this point we can use equations De -t @ of section = 41, n, ... 2na.+ 3n 3 + 4n't.+- 5n$ = so, n, + nz ~ ni -t ~+ n'+ -t" n~ 3n3. + 6n,_+1Q.ns = 45 . (2). But this (45) If ns = o, and n1+ n ~ ~ 9, ~ n2. ~ then n~ .:5: 2, n3 9 9, ==;> 8. But the maximum number of pairwise intersecting = 16, 5-sets is seven. v = 65. (b) r If Us ; O, any vertex of are 15 remaining vertices). C must lie on five 4-lines, (since there But then we must have AG(2,4) on the 16 vertices, which is impossible because this bas disjoint blocks. n 5 > o. So Now we make use of equations ~ a0 + (4). of section + az + a't- = 181, a 1 + 2az. + 5a 3 + 4a 'f = 660, a, + a~ a:r...+ 5a 1 + 6aCf-,. 880. a, + a.2.. - 2a'+ ::A 4-ve~tex -220 9 can only arise from a (since four of the lines on which Each 5-line contains eleven ~ Each vertex of a"'!-~ 110. 5-line in x C in the follo~~ng manner, lies must intersect L outside 4-vertices, n 5 ~ 110 /11 + 1 C can lie ·on at most three = 11. 5-lines, -9 n5 .$. 3.16/5 < 10, a contradiction. C). ( 46) ( c) =15, v =61. r SUppose n.s: '> O. @ , Applying equations a0 + a, + a2.. + a~ + a,,_ = 158, a, + 2aa.. -t- 3a 3 + 4ac.+ :: 560, a2. + 3a~ + 6a'+ ~ a~~ so, ~ n5 ~ = 720. 9. But any vertex lies on at most three n 5 ~ 15. 3/5 5-lines. So 5-lines. Consider two vertices o: The ref ore and any vertex lies on exactly three on a 5-line, viz. This gives at least seventeen vertices in So n~ C. = O. This is the only possible set-up for the ~~ye lines through a vertex. There must then be five one of them. 3-lines such that any vertex lies on exactly This means that there are disjoint 3-lines. 9. (47) (d) = 11, r v = 45. The most difficult case. (i) Suppose ns > o, i.e. Applying equations a 1 + 2a2. + 3as + 4a -c+-:: 240, a7.. .+- 3a ~ + 6a '+ = 240, and a4t = 0 or 6 (since ns : 1 or 2). then We have two possible sorts of x 3-vertices, of these vertices, So D,s ::; 1, n.,.:: x/7, -9 72 y, 7 I x, y n 3 :: y /8, and D2. := of these vertices. y/9, x + y: 80. This is impossible. ''- n't- = 1, (48) = 2, n'S' n4t :: Let p and q o, be the two vertices not in L or M, r= LAM. and let f z. ?. '+ as the remaining vertices in L, M respectively. l Ji: I Then, without loss Y1 , p , zi are the 3-lines through p. Now I f J must be a 2. Then lyl, p , z 3 ) n 5 :: o. { y, , q , ZJ that j Hence 3 1::- Suppose v1e have three 3-line for some z. L, M, and 4-lines through a vertex N. Any line not through and so must be a 3-line. vertices must therefore be Suppose, without loss, is disjoint from this. Then there is one remaining vertex intersect j. z y. and every line through Hence we have another three y or z z must 4-lines through must intersect each of L, M, and The restriction of the lines to these nine AG(2,3). This has disjoint pair can be found which do not correspond to any of our 3-lines and a 4-lines. N, (49) Hence any vertex has at most two Applying equations 4-lines through it and so n+~ 5. 0 nc + n, + n:t -+ n~ + n..,. = 45, n, +- 2n 2 + 3n3. + 4n-r = 55, n:t ~ 3n 1 ~ 6n"f" : 9 n1 + If n't ~ 4, ~ : 2n~ then n1. ~ 8 1 n 1 4-- or But any two of these n't : 5 n2.. ~ 8, n 3 ~ 7. 3-lines must intersect in if there are more than If 55, c, which is impossible 7. we have, L One vertex five q 3-lines. is not covered by any of the 4-lines. But then one of these cannot intersect Hence we know all about mar..imal cliques of size We make use of the _unique geometrisa ti on of Chapter V. It must lie on BG L in r in C. BG S(2,5,v) ls (2, 5, 45 LJ in (50) (12) Normal Cliques. (5) In we defined a normal clique containing a normal clique C. C is covered by Any point of an 0 or k0 S(2,k,v) r +k - 1 : k blocks of C. We must have or a k 0line. k 0 ) k. Any vertex outside and so must lie on (k/k~) The . k0 -lines form a we have an S(2,k0 ,r) Reverting to the contain Any line in the block graph is either a (k/k0 ) C is adjacent to in p.b.d. on k0 C with constant block size, i.e. S(2,k,v), we have that any block not in points covered by the blocks of k - (k/k 0 ) : n C. C. Let C must S be the Then any block not in C of these points, and of course any block And so S is a maximal n-arc of the We have stumbled on a set-up previously investigated by Morgan (23). We note that k~ k0 C on the vertices of the clique. C contains none of them. design. vertices of ·k 0 -lines. set of po in ts covered by !1.o__£.locks of must contain k 0-line k and kD determine the parameters of the design. implies that we have a subplane in the design with r ::- kz - k + 1. = 2 implies that we have a k/2 -arc in AG(2,k) where k is even. (a) k 0- 5, k = 6 requires the existence of an 8(2,6,66) which has recently been constructed by Denniston (8), in such a way that the induced design on the described in (7c). 4-arc is the S(2,4,40 ) We give the blocks of the given by Lorimer and 2 (2,6,66) below , v:ith (51) suffices generated (mod 15). Bo Co Do yo zo A Bl Bio D.s Db yo y 2 c, c~ B2. BS y() y~ Dr D1'2.. C, C2. Y0 Y$ B 't B b c 7 DI\ y D z t c1l. c 5 DI? B 7 Y" z? C" D:!. D ~ D1l. Z0 Zi n.,.~ Bl B\O Zo z'l z'l Bf: C 1 C~ C4 Z0 z., i The thirteen blocks J:li 0 D2. B 11 CS? Y0 z,,_ z i,,z,1 Y2 , YI:., 1-s, Z~, z10 , z12.J + i, Y2 Y" Ys ~Yi , Zt : i-= 0 ,12 and form our normal clique C covering the There are also at least 39 other maximal cliques in the design corresponding to the subplanes in the 39 of each of these cover 26 pairwise intersect points S(2,4,40), and the blocks points. 39 We migi1 t ask whether it is possible to construct an using PG(3,3) as our 4-arc. It does not seem easy to do this, (9). To be able to construct an necessary to find a set of the (b) S(2,k,v) kr/k 0 k 0 ~ 4, a maximal k/k 0 S(2,n,v - rk/k.) of these spreads. on We k/k0 -packing. k ~ 8 6-arc on requires the existence of an 126 points. and one of these is defined on the bilinear form on with a normal clique, it is spreads in the n-arc such that any block lies in might call this a S(2,6,66) 8(2,8,176) which has There are at least two known 126 8(2,6,126) isotropic points of a unitary PG(2,25). We consider this design in some detail. be a representative of a projective point in is said to be isotropic if Frobenius automorphism of iX + yY + GF(25). zz -: 0, Let (x,y,z) ~ GF(25) PG(2,25). where l Then this paint x = x 5 is the Clearly this is a good definition. J (52) Any line of Let PG (2, 25) can be written in the form represent this line. [a,b,c] l (x,y, z): ax+ by+ cz =0 1. Then by a slight abuse of language we will call a line isotropic if the point (a,b,c) is. Clearly, by this duality between points and lines, there are the same number of isotropic points as lines. The group PGU(3,5) of automorphisms of PG(2,25) preserving the unitary form is doubly transitive on the isotropic points. be isotropic points. (u,v) 3-dimensional nonsingular So by normalisation we can assume (u,v)= l. that u,v and w are independent and span the space. we would have a totally isotropic <u,u) :(v,v> :. o, Let be such v1 [wJ , i.e. (u,V1) =-<v,w/: O. lie in the line u ~ v =L u;vi f O, otherwise we would have a 2--0.imensional totally isotropic subspace of a space. Let Again < w) f w, 2--0.imensional subspace. (u,v) =(w,w> :: 1, Then 0, u,v otherwise So we have (u,w) =(v,Vi):: 0. Any pair of distinct isotropic points can be extended to a basis in this manner and there is clearly a unitary mapping taking one basis to another. In a similar manner PGU(3,5) is transitive on the nonisotropic points and lines. Let us abbreviate to n-points, -lines for nonisotropic, and i-points, -lines for isotropic. Let n-line w ~ GF(25) [ l ,O ,o] w 1 'l : be such that 1, w' = -1. Consider the Suppose it contains an isotropic point Then this is isotropic if and only if ~ z z: So any i-line contains 6 1 + z 6 : 0 (~ z-' :: -1, is a primitive 'i \'i ' i i-points. (O,l,z). 12tb root of unity, ~ f 1, 3' 5' 7 ' 9' 11 3. (53) Consider the Any other point (x,y,z) on the line is such that {, x 6 .+ y b + z (,. :: x b +w " z " +- z 6 : x, Then So any i-line contains one Then, since any 25 (O,l,w). y + wz '= O, or y: -wz. x = o. i-point. n-line contains 6 B n-points,lines. and i-points, and any i-point lies n-lines, 6B :: 25A so A = 126, and B (l,O,O) therefore disjoint in any of these 20 I, I, the set of 126 to S (2,6,126). n-lines 20 n-lines whose r estrictions are I form an I, and the remaining six points of (0,1, wi.) lines are [1,0,0] a spread of I. blocks of i-line, we -obtain a on 525 lies on these all lie on the line 21 =525. PGU(5,5) i-points, the restrictions of the Furthermore A + B = 651, also By t he double transitivit;:,; of on an i-point which is only zero if A i-points,lines, Suppose there are on It contains the i-line [0,1,wJ . wbere not on i l: { 1, 5 ' 5 ' 7 ' 9 ' 11) and So to any n-".-point there corresponds Finally, considering the 1-packing of 25 n-points I. However, for our construction we require a 2-packing of 50 spreads, such that no spreads have more than one line in common. Consider the It contains 25 i-line n-points <(2,1,x),(2,l,y))":: 0 So if p,q t he spreads are are S( p) x = 2y, i.e. [1,-2,0] (2,1,x), and ( 0 'O, 1) • <=> xj-: Ol.:=;>x-:. 0 or y:: O. n-points on the same and x 'f 0, S (q) i-line then ( p,q/ =f have no lines in common. n-points such that (p,q> ~ o, -then p and So if o, and so p and q q lie on some n-line (54) [r J and furthermore q So S(p) and S(q) E:. LP] ~ [P] € S(q) and have two lines in common. [ q] E: S (p) similarly. This shows that we cannot find a set of fifty spreads with our required property, which all correspond to n-points. these, and consider the another spread, say S(p) and S(q) (13) n-line S(q). [P] ~ S (p). Then But then (p,q):: o, s(p) Let [ p] be one of must lie in which implies that have two lines in common. So to construct an other spreads. For suppose we could. S(2,8,176) from this design we need to find I have not been able to learn of the existence of any. Steiner Sys terns w:i th The methods for k ~ 6. k ::: 3,4,5 used in earlier sections in this chapter become very long and tedious for k~ 6. (55) CHAPTER IV. BG [sl. (2, k, v )] (1) FOR GENERAL ')\ BGlsa(2,k,v)] A> 1 When for AND NONUNIQUE GEOMETRI SATION. ~>l. there is no guarantee that the blocks of the design have only two nontrivial intersection numbers. N is the Considering the design as a subset of the Johnson scheme J(v,k), point-block (v x b) incidence matrix of the design, N N.,- = (r - A) I f +'A J • A (v - k) I (k - 1) NTN i:D the Ak_., B·l 1 s and In fact if + JJ . where iB·I are adjacency matrices of subgraphs of the Johnson relations Bt< is the b x b identity matrix (assuming that there are no repeated blocks). In general we cannot d·efine an association scheme on the blocks of the design, (as we could in Chapter III), but it is possible sometimes, and if the design has only two intersection numbers we are guaranteed . a strongly regular graph. I, section(7). Such This is a special case of a theorem in Chapter 2-<l.esigns are called quasi-symmetric and were introduced .and investigated by Goethals and Seidel (14). these first, because of their greater structure. We shall consider (56) (2) Quasi-symmetric designs. We give a proof, found in association scheme. NTN : hence Let x< y 1 be the intersection numbers of the design. x(.J .-::I "'."" , B)-+ yB +kl, B -:: NTN - (k - x) I - xJ y-x and so (5), that the B. 1 s form a 2-class ' B has eigenvalues, J/ (y - x) once , J/ (y - x) v - 1 times, b - v times. [rk - (k - x) - xv ~ r - 7\ - (k - x) -(k - x)/ (y - x) Therefore B is the adjacency matrix of a strongly regular graph since it generates a 3-dimensional algebra. Since the eigenvalues are integers, we must have and (y - x) (y - x) J (k -:, x) I (r -A). The first of these conditions is similar to the second part of the theorem of Deza, Erdos and Frankl (see Chapter II). We wonder whether this holds more generally for designs. Suppose x > O, then any two blocks intersect, so we are not going to be able to extend the Erdos, Ko, Rado theorem to this case. Hovl8ver (57) A, and count consider a block (p,, p 2 , B) such that p , p 1 2 f A, ?\ (v - k) (v - k - 1) ~ rk (k - 1) (k - 2) , which implies that v ~k 1. - 1, and is a very generous bound. x> 0 are no quasi-symmetric designs with x = o, If of the design. y we look at the set of two intersect in f;ny r So there and blocks through a point p points, and (ignoring the case y =1, which only occurs if it is a Steiner system), they intersect in y - 1 points apart from through p, p. So there is a = 1 + r (k - 1) /A. ~ So if v > k 'l- - 1, k v points, and (y - 1) 2-. y ::>1 and of block-size k. J (k - 1) /\ -k+l. there are no quasi-symmetric designs with block-size However we can do better in the case when So if on the blocks ').. ~ k - 1 (Fisher's inequa.li ty). + [1 + ( ~ - 1) (k - 1) 1 k on 1 and therefore, (y -l)(r -1)::: (A-l)(k -1), ~ v s _1 (2,'A ,r) k x =. 0. Vie need y } k. is a prime then there are no quasi-symmetric designs We are interested in families of pairwise intersecting blocks. Using the clique bound of Chapter I, (58) + (r - 1 )ky w ~ 1 + d/-?i:L = 1 :- r , r, and by an argument yk and so again such families have maximal size similar to III (1), cliques of size r are regular vd th nexus k(k - y)?d?..- 1) • (r - 'A )y(y - 1) The block graphs of Hadamard 3-designs (th ese are quasi-syJJlilletric 2-designs) a r e the complements of a families of r 1-factor, and so it is easy to find pairwise intersecting bJ.ocks, in this case. Note: There are on the whole ve"I"'J fev1 quasi-symmetric designs. We list possible parameter values for k ~ 12, x '::: o, y ~ 2, SS(2 ,6, 22) y:: 2, Ss(2,6,12) y-.:.. 3, s't-( 2' 6' 21) y:: 2, s (2,8,16) y.:4, 7 S"t(2,9,27) Sc,(2,10,20) y:: 5, S (2,10,70) 0 YI:' 2, s., (2,12,24) y::: 6, s 11 (2,12,57) 1=- 3, s (2,4,8) 3 (3) Cliques of size r in y~ 3, BG 11 y /' 1. s.s (2,12,100) y~ 2, El1 (2,12,112) y:: 2. isomorphic 11 to the set of r blocks .· through a point. The set of r blocks through a point have certain properties when regarded as a clique of size r in the graph v:i th ad jacency matrix P , -.l (59) For instance, for any block ~ c, B in the clique (r - 1) ~ ('A - l)(k -1). When considering nonunique geometrisation of the block graph we .shall be looking for such cliques of size Let point p r. x F be the number of blocks of of the design. least one block of C. Let h containing a particular be the number of points covered by at Then, = h, rk, Now by analogy to equations 0 when A= 1 in L [xp - A ((v -(k1) - -rl)k(k - i/\)j1'"1.. = h /\~ 1 l III(2), we have '2. (v - l)k (v - 1) + (k ·- 1)4 (60) So h is a minimum of (v - l)k (k - l)~ (v - 1) + x'f :?.[(v - 1) + (k - ltl when the blocks of ( 4) C. for any point J (k - l)k 1... BG[sa(2,k, v )] BGLs>.(2,k,v)] v r covered by And so we have again characterized normal cliques. Nonunique geometrisation in to the sets of p has a set of cliques of size r corresponding blocks through points of the design. These cliques 'A have the property that any two of them have common, and each edge of Bi blocks (vertices) in is contained in exactly are said therefore to geornetrise the block graph. we can find another set of · · v Suppose we can. i of them. They We want to know whether cliques with these properties. Then \'le can form the v x b incidence matrix N2. of these cliques against blocks, i.e. if B E. C, otherwise. Let N, be the pcint-block incidence matrix of the design. Then T iBi '; N, NI N z NI ::. 2 (r -A)l + J -::'/\[(v - k) I+ (k - 1) .r]:: N1 1~ 1 1 (61) Now consider the and so v x v matrix, X(p,C) = the number of blocks of the design which contain p C. and lie in the clique T x x = N, N-'r Ni N, : NI 'T T N, NI' N, N, = ':; Therefore (#. iBi) NT I ((r -'?\)I +'71.J y· X satisfies a matrix equation similar to that satisfied ·by the incidence matrix of a symmetric design. In the particular case when all the new geometrising cliques are normal, X(p,C) ~ I\ k :.'Ar(v - 1) + (k - i) l 0 = 0 Then J: if p otherwise. Y : X/k 0 A is a y k(k - 1) 1 y T = (0,1)-matrix and satisfies is covered by a block of C. (62) In other words, :.' there is a symmetric design governing the incidence be tween points and cliques, and the parameters of this design depend only on and and are independent of A . k Note: We say a point there is a block Let r v k0 p and a clique B such that and n :. k/k 0 C of a design are incident if p E B E C. be given. v :.'i\(nk 0 (k 0 :?._(nk0 (k 0 - l)+ l},, Then - k :. nk 0 , 1) of- l)(nk 0 - and 1) + 1. In this instance there is nothing to be gained by applying the Bruck, Ryser,Chowla conditions, because the equation is always satisfied by Y [(r -A ) ~1A. JJ ~L . A.k. (5) I eometrisation b We know that for some S(2,k,v) normal cli ues in k , for r :. k ;. 1 and BG S 2 k v) r -:: k ~ - k-+- 1, an exists whose block graph is geometrisable in more than one way and t be cliques of the second geometrisation are normal with respect to the first and vice versa, ( III(6) and (7) ) ~ · Furthermore in both cases there is a symmetric design between the points and the cliques. We examine the possibility of such an alternative geometrisation by normal cliques for other values of with the case (2,k,v): (2,6,66). r (as a function of We prove t ha t there is no k) beginning S(2,6,66) whose block gra :; h has t his structure, although as v:e have seen, · th ere is (63) a design with these parameters containing at least one normal clique. (a) Proposition: k/kD lies in exactly Any point-block pair There are 0 k0 or p which meets B and A. are exactly such that k cliques which contain blocks through B, (there are k p. B and each of these But for any block cliques containing p c, covered by the blocks of a normal clique k: 2k 0 , consider the Take one of these , C1 C1 following. cliques containing a block. S(2,6,66) and suppose its block graph has (66,26,10) Then the point-clique incidence symmetric design. points in common, (i.e. there are 10 blocks of both). Bt c. They all contain the block, and any other another geometrisation by normal cliques. exactly 10 which lie in any block is contained in exactly one other clique. Let us now consider an is governed by a k/k 0 points say, and consider .the intersections of the k - 1 other cliques with this one. point covered by k So there B. and Note: This is the dual of the fact that there are (b)So, for A through such), there is a unique clique containing They meet in a point, so they meet in a clique. k/k 0 pf B, cliques. Proof: contains (p,B) So any two cliques have points covered by the They also have one block in common, so we have the (64) c1 Cic c2 and have the block B in common and four other points Suppose X' (if j ~fl,2,3,(~, But then A Similarly At c, lie on a block J k: 1or2 ). C~ • or of c~ C1 In which case x~, in the 8(2,3,13). 5 covered by c,, ~' C1 is an S(2,3,13). C, which contain ~. containing can be divided into Now x, , x 2 , x B in 5 3-lines B. S(2,3,13) 3-lines each which 3-lines not . _· .. parallel classes of four 3-lines. C We must now check that neither of the two nonisomorphic S(2,3,13)'s One such So in the In other words the set of twenty This can be done for any (c) • B and any point gives rise to a set of four disjoint do not contain xg C1 There are and so correspond to four disjoint lies in exactly one of them. c2 , •••••• ,c4 x_...,.lie in a block The remaining vertex is that corresponding to cliques apart from C1 c1 • . have two blocks in x~, x1 , A E: B. . in no block of There are of C1 , and so 3-lines corresponding to the points covered by x~ lie which is in A A must intersect C~ and Hence no two of The dual design on the blocks of 26 Then contains at least three points of common, a contradiction. of and (see Hall(l6) ), have this special resolvability property. 8(2 1 3,13) bas blocks as given in the first two columns following and the other has the blocks of the second two columns. (65) A B 0 2 8 1 5 4 0 2 8 e 5 4 1 3 9 2 6 5 1 3 5 2 6 5 2 4 t 3 7 6 2 4 t 3 7 6 3 5 e 4 8 7 4 9 1 4 8 7 4 6 .w 5 9 8 4 6 w 5 9 8 5 7 0 6 t 9 5 7 0 6 t 9 6 8 1 7 e t 6 8 1 7 e t 7 9 2 8 we 7 9 2 8 w e 8 t 3 a 0 w "' 8 t 3 9 0 w 9 e 4 t 1 0 9 e 3 t 1 0 t w5 e 2 1 t w5 e 2 1 e 0 6 w3 2 e o 6 w3 2 w1 7 0 4 3 w1 7 0 w3 We consider the twenty blocks which do not contain the point possible to find parallel classes of four blocks, i.e. e 8 w, 0 5 7, in 1 5 9, 6. It is 2 4 t, A. First we need a proposition, Proposition: Given four disjoint blocks of an below cannot occur. S( 2,3,13), the configuration (66) Proof: First possibility; Dualising gives the following set-up, which requires at least points, i.e. 28 28 dual- blocks in the design. Second possibility; Dualising gives the following, which this time requires Hence neither of these configurations can occur. 27 blocks. (67) Consider the blocks of blocks through 6 2 5 • So A first, and the block which intersect 6 5 3 , t , and 7 9 2 are 7 9 2. 6 7 3 The three 6 9 t , and must lie in different blocks of the parallel class containing 7 9 2 , by the proposition. The only block containing 3 , disjoint from 7 9 2 , and not containing 6 , t , or But now all the blocks through contain 5 • t more we have that 3 , t and parallel class not covering B, and the block 6. As in A 3 0 4. class containing So neither have an 5 3 0 4 , or contain 7 9 2 or 7 9 2 or 7 9 2 2 3 O4 • or 7 9 2. again. Once must lie in different blocks of the The only block containing 3 all the blocks through intersect or t • 5 that will Hence there is no parallel and not covering S(2,3,13) S(2,6,66) 6 7~ 9 is 3 O4 Hence there is no parallel class containing Consider now the blocks of suffice is intersect 5 6 . is resolvable at the point 6 . So we cannot whose block graph has an alternative geometrisation by normal cliques. It is possible to prove that a necessary condition for the exis~ence of an S(2,k.,v) r , with with nonunique geometrisation by normal cliques of size k: 2k 0 , is the existence of an resolvability property, i.e. for any point cf the not containing that point are divided into (r - l)/k 0 S(2,k 0 ,r) k - 1 with the special S(2,k0 ,r) , the blocks parallel classes of blocks. The next case existence of a k ~ 8, (176,50,14) k0 = 4, v ~ 176, r ~ 25, requires the symmetric design, and a special I have not been able to determine whether such an 8 (2,4,25) S(2,4,25). exists. (68) (6) An Sa(2,8,176) whose block graph is geometrisable in two ways. M.Smi th (28), following the wor~ ·:of G.~Higman (17), In her thesis, considers the doubly transitive representation of the Higman Sims group on 176 points. It turns out that there are two such representations, and a subgroup of index 176, isomorphic to PIU(5,5~), which does not fix a point in one representation, has two orbits, one of size the other of size 126. If we consider these sets of size obtain a symmetric block design on the 176 50 50 and we points with parameters (176,50,14). s 1 (the symmetric Furthermore the group bas subgroups isomorphic to group on 8 letters), and these have orbits of size 8 and 168; (this was the method used by G.Higman to construct this representation). 8 , we obtain an we consider the orbits of size and because the stabiliser of each block is in O,l or 2 points. S~ 8~(2,8,176) If design, , the blocks must intersect (If they intersect in more, the condition that any two points have exactly two blocks through them is violated, by the 8-fold transitivity of the block stabiliser on the points of the block). The blocks of size 8 8 , called conics by Higman, lie in exactly 50 of the sets of size of the symmetric design, (called quadrics S~(2,8,176) by Higman). So they give an incidence. Finally any quadric contains exactly of which intersect in 1 or 50 in BG[s 2 (2,8,176n cliques of size 2 points. geometrisation of the block graph. covering the minimum number, 50 on the quadrics with dual 50 conics, any two So we have a new set of 176 corresponding to another Furthermore the cliques are normal, , points of the design, and regular, (69) any other block containing exactly two of tbese points, intersecting 14 of the blocks in one point, and one of them ~n two. The structure of the 50 bJ,"C)cks of size 8 intersecting in one' or two points is that obtained by taking the Moore grapb of valency 7, and constructing 50 blocks as follows. be that vertex together with the 7 if For any vertex adjacent vertices. x is adjacent to y, if not. x, let B~ Then clearly, (70) ·cHAPTER V AN ASSOCIATION SCHEME FOR THE 1-FACTORS OF THE COMPLETE GRAPH, AND CLIQUES AND DESIGNS THERErn. (1) Definitions, and the Centraliser Algebra of a Permutation Group. A 1-factor of graph on given of 2n K 2~ is a collection of n edges of the complete vertices, such that any vertex lies on a unique edge. A 1-factor can be identified with the fixed-point-free involution S~ which interchanges the pairs of points that make up the edges of the 1-factor. The natural action of the symmetric group 1-factors of is permutation equivalent to its action by conjugation K2 ~ on the S2 ~ on its fixed-point-free involutions. The Centraliser Algebra of a transitive permutation group a set D_ of size v, is the set of v x v matrices over the complex numbers which commute with all the permutation matrices of group ~ G has rank m+ 1 on G on G. If the .fl. (i.e. the stabiliser of a point has orbits on the remaining points), and the centraliser algebra is commutative, then the orbits of G on the 2-subsets of m-class association scheme, as defined in Chapter I. notation of Wielandt (30), for any orbit ~ the point 1, otherwise. In fact, using the of the stabiliser we can associate the following matrix if there is a ll form an G1 , of Al:::. , where, d € 6. , g ~ G such that (l,d)g :: (a,b)ft (71) It is not difficult to show that these matrices generate the centraliser algebra of the representation. Furthermore the sum over distinct orbits of the corresponding matrices is the all 1 matrix J . So if the algebra is commutative it can be regarded as an association algebra with m classes. g € G, let For each by the action of A: Theorem g on P(g) be the v x v permutation matrix defined fl . G on .() is commutative if the permutation The centraliser of G Proof: :J 1 , D2 , • • • • • ,Dt" Let on D character of is the sum of distinct characters of be the irreducible constituents of the permutation representation on i l any v x v G. permutation matrix , i.e. P(g) in for some unitary matrix U, G has the following decomposition, 1 U- P(g)U with 0' s outside the blocks on the main diagonal. the form _, U P(g)U We write this in· D -i. ( g ) , . . • , D~ ( g ) , • • • • . . . . . , D,.(g), ... ,D,..(g)J \. v--l ei. I... -.- e,. ) (72) Then, if where Q is the centraliser algebra, e 1 :. 1, we.== the ring of all e;x ei matrices over the complex numbers, l Tfi:. the identity matrix of size f,c. , the degree of the i-th irreducible, and x represents Kronecker product. Clearly this is commutative if and only if For the i-th conjugacy class f.i of G, ei~ 1 for all define the i. i-th class matrix, c~ = L,1 P(g) g~~i Tb.en we have; Theorem B: All the class matrices belong to the centraliser algebra They commute with each other. Furthermore, the centraliser algebra is commutative if and only if the class matrices generate Ct . Proof: c.' l for all h ~ G. Cl. . (73) So if the class matrices generate ()__, it is commutative. Conversely, suppose Q is commutative. Ynen from theorem A, the representation has distinct constituents. Consider value of the LX, (j )] , the character table of i-th character on the G. ( xi (j) ~ the j-th conjugacy class). It is well kno\'m that its columns are orthogonal, and so , as a matrix, it is nonsingular. In particular, if we look at the matrix formed by the rows corresponding to the irreducible constituents in our permutation representation, it has fUll row rank, independent columns. m+l m+ 1 , and so it has a set of Consider this square submatrix, which with suitable renumbering, we can call [-xi (jil i,j : l, •••••••. ,m+l. It is nonsingular. Again, from the basic representation theory, and so, (74) is nonsingular, since Therefore the are independent. But dim a= + m 1. Hence they Cl . span Theorems (2) CJ Is A and B can be found in The character of Szn on the Wieland t .. ( 50) • 1-factors of K2 ". We give the proof of a theorem by Thompson (29), proved in a very different manner by Sar.J. and James, see (27), but perhaps known earlier, concerning the constituents of the permutation representation of on the 1-factors of Theorem C: xtrr) Let Kz~· ')( be the character of this representation, and let be the irreducible character of partition S~~ s :Z'\ corresponding to the 1T . ..Then if every part of "Ti is even, otherwise. In particular this representation has rank of p(n), the number of partitions n. Proof: (due to Thompson) (a) ( 'X, 'X ) = p(n) in the next lemma. is not difficult; we do this in detail (75) We need to show (b) even. if every part of TT is To do this we make use of the methods of the representation theory of the symmetric group over the complex numbers; see, for example, CUrtis and Reiner (6). Let k-:: 1 T be a tableau associated with 1T • to 2n, we have a position Then for each (ii<, j'IC), where the number of set k can be said to lie in the tableau. For each edge e :: 1k , ~ J l~ hT ( e ) = j K 2 ,.,, - j{\ , an edge of u v'f ( e ) : If u is a 1-factor, set ~(u) = max e Since every part of -rr is even, o, h~u(T)) : e.g. for "1-( e) = max h.r(e), e there is a unique w7 (u(T)) -:; vr ( e) edge of u 7 u : u(T), such that 1. 2n ~ 6, T a:: Let C , R be the largest subgroup of respectively row, Set e(Cf ~ of S~~ which fixes each column, T. \cj9 £ sg(c) c ' c c 1 !; e(R) + ~ rRf':[ r, r~ R ~ ~ e(T) = e(C) e(R) then e(T) is a principal idempotent of (76) the group algebra QSZn , and QV. e(T):: (')(, )((1T)) , dim ~here is the vector space spanned by all the V V.e(T) ~ 0. We need to show that in 1-factors of 2 K ~. We show that the coefficient of u(T) u(T).e(T) is positive. Let f(T) = L_ sg(c)cr. = e(T) c E; c rf. R The coefficient of u(T) in u(T).f(T) is ~ sg(c) (c,r) c E C, r '- R er fixes u(T) Suppose c € c, Then ( u ( T ) ) er -:. u ( T ) , But r ER, er fixes u(T) .c ~ u(T) .r _, . and w1 ( u ( T) • c) -:: wT (u ( T) ) :: 1, (since the functions u(T). wT, h,- are constant on C-orbits, R-orbits, respectively), and so _, u(T).c:: u(T).r Let C I • C 2 • • • • • • C 2. ~ • I • C 2f ' C ':: T, and c.I odd. u(T). 2f moves only the points in column acts on column i i where ~ Hence u(T) ~ u(T).1.1 in the same way as sg(c 1 ) : sg(ci+-t). Ci+ 1 Eence is the number of columns of i. Then,obviously, acts on column sg(c) = 1. V!e c.I i + 1, for certainly have and so the result follows. We have included t his proof be cause r.e gener alise it J ater v:hen (77) considering designs in the scheme. (3) A useful lemma. A and Theorems C together imply that the 1-factors of give rise to a scheme with Theorem p(n) - 1 classes. K 2~ The main point of C is that it identifies the eigenspaces of the association scheme with certain irreducible representation subspaces of give a prcof that the rank of the representation is p(n) S,i""· We which will also be of use later. fL, f~ Lemma: Let f1, Then 1) For every partition between the .be 1-factors ff,, f2~ , and fr,, Oc s2 "' such that there corresponds a relation r3)E R(Ti) 3) There exists o-~ s2"' such that 4) There exists 2n points and components of length points and such that then there exists s2."" such that () €: f~ er:: r, fixes at least n has x r, er: f 2 and cs r 1o-:: f2. • 2, then there are exactly i.e. n and In fact, if Proof: of 1-factors. · 2) . If of the 11 K~~· of f, + f2. and y (for definition see below) components of length greater than two, 2::/ permutations cr- '= s2 "' which fix n ~ x f 1~:: f 2.. 1) . Take any two 1-factors f 1 , fz: their edges taken together, f 1 + f,, cover every vertex twice and so form a collection of (78) disjoint circuits of even length (including length 2, <::>) and so we 2rr of 2n into even parts, and so obtain a partition Ti is a n, 2ii is a partition of n. Conversely, given a. partition partition of 2n into even parts, and it is not difficult to find 1-factors r,, fL constituents of 2) such that the circuits of Tr of f1 + f2. have lengths the 2Tr. f 1 + f2. Suppose f 1 + f 1 have as components circuits of and the same lengths, i.e. they both correspond to the same p~rtition of f 1 + fl., Consider first just f 1 + f'l., and the longest circuit of length Then any point in this circuit lies on one edge of 2rn 1 say. f 1 and one edge of and label it a1 • a~+l· the next point a2.. c 1 , of Pick an arbitrar; point of the circuit Then go along the adjacent point c, f.,_ • f1 Then go along the edge at f~ a,, and label the edge at an+I a 1 1 • • • ,aM,,at"l-t-1'. •.,an .,.W\, • label the other circuits similarly, so we might have for ~l>/~b<~J ~t><1 ~7 f, q,C> 4:1.'t a..d' edges are·continuous and of n, fixes 3) f 1 + f '2 and f1+ fl CJ"'- s 2 "' such that r, fz to For each circuit n ':: 6, a., l <=41'1.. f 1 + f3 with labels b1 , ••• , b2 "'. correspond to the same partition there is a and maps ~II al~ b 1, i =1 to 2n, which f.3 • of Now f 2.. edges are dotted. Now produce a similar labelling for Then because and label Continue in this manner until all the points of have been labelled, with labels where n. f 1 + f, choose an orientation (79) of the points of c. Then f:5":: TT¥(ci) is such that f 1 l)': f 2 and f:2.c-:f,. 4.) In the same way as in f1 + f 2 of of length 2r a-es ~ edges of to those of f1 2 consecutive points of Then (a 1 ,a 2 , • • • ,a,..) wbich fix at least which maps the edges of f~. f1 c. r points of and points of (a~r-_, •...• ,al\+I) c and map the Now, clearly, there can be no to the edges of So any such c , fixes alternate points. er~ S,__~ f2.. , and fixes two fixes at most <5 c , and no two consecutive ones, and so any r c greater than two, and label the vertices a 1 , • • • • ,ar,an+t'····,al\+I". are two such 2) we consider a particular circuit <S r points of v;hich fixes exactly So anj edge of f 1 has one of its points fixed, and so the other point in the edge must go either to the point two ,to the left in an orientation of to the right. This determines the action of the only way we can have . (Y mapping fI to c, or to a point two er on the circuit. f L. and fixing Finally n + X points, is for it to fix each repeated edge and act in one of two ways on each circuit of length greater than two. 1), 2), and 3) with p(n) - 1 4) (4) Hence the result. are enough to show that we have an association scheme classes. will be of use later. The eigenvalues cf the scheme. For the Johnson and Hamming schemes the eigenvalues are known in terms of the basic parameters and the Krawchuk and Eberlein polynomials. It does not seem possible to provide such a neat closed form for the (80) eigenvalues of our scheme, but we present a method for finding them, making use of theorem B. Clearly the class matrices here do not form a basis for the centraliser algebra, and there is no unique way of representing the Ai 's as linear combinations of the c41s. can be found in terms of the CJ 's for only those conjugacy classes whose elements fix at least expression is unique. n However, a canonical expression points, and in terms bf these The reason for this is part 4) the of the preceeding lemma. Now the number of conjugacy classes whose elements fix at least points is exactly p(n) , and it turns out that we have a triangular system of equations connecting the the A;'s, CJ 1 s, and Let A(li) such that in E~'s CJ's Ai 1s. and the by partitions of '"'ii be a partition of n First we index as follows: n • is the adjacency matrix corresponding to the relation R(1T) fr,, fz.)~ R(!r) if the circuits of f 1 +· f2. have as lengths the components of C(Ti) n 2Ti. is the class matrix corresponding to the conjugacy class S 2.tl\ whose cycle lengths are components of 'iT together with n fixed points. E(T\) is the projection matrix of of which is isomorphic as an arising from the partition conjugate to I I . ~ne v onto V(2ir?, the eigenspace (2 Tf ') s 2 ""-modu1e to the Specht module s 2(li') of 2n , wh ere Tr' is the partition ordering of the partitions I\ of n follows that used by D.E.Littlewood (20) in his character tables of the symmetric groups. (81) The eigenvalues of the C·1 's on the irreducible subspaces are we11 known, and are easily calculated from the character table of 2 , or s ~ if this is not available, by the methods of the representation theory of the symmetric group. We have, Yne main problem is to find aid ts such that This is done for the cases n :. 4,5,6, but beyond this point , the calculations become very involved. ( 5) Computing the a i.( 's. We recall Ci (f1 , f~) =- the number of So e. a i J -:. the number of then For small n, l f 1 cs : f 2 f 1 t:f' = f 2. • such that if • and for some method for calculating the increases rapidly with such that i and aiJ 's. n , and for j , this is a relatively sati.sfactory However, the length of these computations n ~ S,6, the following shorter method was used. The underlying idea is to pick a particular number of (J'" E. e. I such that f1 and to count the (82) b lJ , Calling this number we have The calculation of the b;J 1 s e.' number of falls into two parts. which contain certain edges of First, we find the in their cycle f, structure in a prescribed manner, and then we find the number of ways in which we can choose such edges. is vrith an example: The best way to illustrate the method we do the case where n = 6, (1, 7) ( 2 1 8) ( 3 1 9) ( 4, 10) ( 5' 11) ( 6'12) f I ': First, there is the case where the from each edge of the 1-factor. lemma, this gives rise to a, 7 6-cycle consists of one point As we have remarked in part 4) of tbe = 2. Second, there is the case where the from one edge of the four edges of the 6-cycle contains 2 points 1-factor and four other points, one from each of 1-factor. Then we have three subcases, I,_~.-_-..-, '·\ I \~ I s ...' ' \ 48 (!" such that R~ , I I Lf. ..__ - -· '3 It~-·'2. \ $ / I ' \ \. 7 I \ \ I 'S-~ I \ '\ \ R(o ' I tt ·- - -· 3 S I 48 I I 4•- - - l \3 I giving a 1 ,c. = 120.6.5.2"" ::- 25 2504 (83) Third, there is the case where the the 6-cycle contains two edges of 1-factor and two other points, one from each of two of the remaining edges of the 1-factor. I ,---('1 . Then we have 8 subcases. \ 'f\.___j'I \ '!- --•,? I \ \ i +\ )~ g"r= - =-'2. 'F ~7 I \ ~ These contribute I 1. 80 .15 . 6. 2 :; 40 A~ 720 '2 16.15.6.2 : 180 . 8 R3. 16 R"+- 16 R4 'Z 24.15 .6 ·~·2 : 160 32 AJ.t. 54 A'1 (84) Fourth, there is the case where the the 1-factor. I We then have 5 48 . R1 6-cycle contains 5 subcases. 1 The se contribute 24 R i. 48 . 20 50 24 R~ r: 52 A I 64.20 ::; 8 A2. 160 8.20 = 160 A 0 8 From all this we obtain, (6) The eigenvalues and the Case n ::. 4 - p(4):: 5. a;i's. edges of (85) (1) Co .. AC> -- (12) c. = 4A (125) Cz.= (1234) C5 .:- 12A 0 + 2A, -t 9A'L -t 2A 1 (12) (34) C-t: l8A0 -+ 4A 1 + 3Ai + 4A+. 0 I + 2A 1 4A 1 + 2Ai.. P matrix l't 2 12. 3 1 4 2 2 \?1 1 12 32 48 12 1 (?,2] l 5 -4 8 -2 20 (4""] 1 2 8 -2 7 14 l_4,2~] 1 -1 -2 ~ 4 -2 56 [2-r] 1 -6 8 -6 3 14 Case n :. 5. p(S) ':. 7. (1) Co :: (12) (123) c, = 5A 0 + 2A 1 c, ~ 4A 1 +- 2A2. (1234) C.!>: 20A 0 + 2A 1 + 9Az. + 2Ai (12) (34) C+=- 30A 0 + 6A 1 + 3A2. + 4A~ (12) (345) Cs : 36A, +10A2. + SA~+ 16A.,_ -t 4As (12345) c,:: 24A I+ 12A~ +l6A3 + 2A' • Ao "f matrix lS" 2 i1 3 1'1. 4 1 22.1 2 3 5 l]_o] 1 20 80 240 60 160 384 1 f s,2] 1 11 26 24 6 -20 -48 35 [6,4] 1 6 -4 -26 11 20 -8 90 [6,21.] 1 3 2 -8 -10 -4 16 225 [4 ,2] 2 1 0 -10 10 5 10 4 252 &,21] 1 -4 2 6 -5 10 -12 300 [2s] 1 -10 20 -30 15 -20 24 42 (86) p(6) = 11. (1) Co :: Ao (12) 6A 0 + 2A 1 (125) c, = c2. -: 4A 1 + 2A~ (1234) C3 : 30A 0 + 2A, + 9A 4 + 2Ai (12)(54) C~: 45A 0 + 8A, + 3AL ~ 4A.,_ (12)(345) Cs c 48A I + 12A2. + 8A 3 + 16A 4 + 4A, (12545) c, = 52A I +-12A 2. + 16A'! + 2A(. (125456) . C7= 160A 0 + 52A 1 +62A2. + 40A ,.+ 52Acr+ 25At. + 2A 1 (12)(5456) (12) (54) (56) c! = 120A0 + 64A 1 + 66A, + 28A .3 + 24A't- + 18A S'-+ lOA & + 4Ap c., = 140~ +- 56.A.., .... lOA i. + 4A, +- 8A't + 6As +- 8Acr (125) (456) c,o:: l60A0 + 22A l. -t 8A\t + 52Att +- 8As + SA, + 4A Case n ... 6 • 3 10 • 4 1 2 1 2 5 1 5 1 6 2 4 ..2~ ·5 160 720 180 960 2304 3840 1440 120 640 1 19 72 192 48 80 192 -584 -144 -12 -64 54 1 12 16 -18 27 24 -144 -48 108 50 -8 275 [6,6] 1 9 -8 -78 55 120 -48 -24 -114 -27 136 132 [8,2~] 1 9 22 12 -12 -60 -48 96 -24 - -12 16 616 Cs ,4, 2J 1 4 -8 -18 5 0 32 16 -4 -2 -24 2675 (4 t] 1 0 -20 30 15 -60 24 0 -60 30 40 tG,2 ] 1 0 4 -6 -21 12 24 -48 12 6 16 1925 l_4\2~J 1 -5 -8 24 5 0 -24 -12 24 -9 4 2640 8,24] 1 -8 12 -6 3 20 -24 48 -36 6 -16 1485 [2"] 1 -15 40 -90 45 -120 144 -120 90 -15 P matrix 16 2 l '+ 5 1 [12] 1 50 [10,2] 1 [8,4] 1 ~ 2.. 40 462 152 (87) Note: R~oth has calculated these P-matrices directly by co~puting the 's - a monumental task - and the fi~res we have arrived at independently P·t lq' IC. have each served as useful checks for the other. (7) Designs in the Scheme. In analogy with the Johnson and Hamming schemes, we wish to consider t-designs in this association scheme. Let us call a collection Y of 1-facte;rs a t-design, if for any collection of there are a constant number of t disjoint edges of 1-factors in the set K2"'", Y which contain these edges. Consider the matrix NL '!;,W\ which has columns indexed by all the 1-factors and rows indexed by sets of t 1 Nt, •...(e, f) = [ disjoint edges, and if the edges of e are contained in those o. otherwise. of f. If ¢,, is the characteristic vector of Y, the eondition that y is a t-design can be written or (Ne""" - ) 1 ::. o, k 'i\ J, J "'""' cp,, for some constant k. So we need to find out which irreducible representation subspaces make up the row space of NL c:,'"""' • (88) Lemma: N be an n x m matrix over tbe complex numbers with the property that a group G acts on both the rows and the columns of N. i.e. Let g ~ G, if for all rows, and Q(g) P~g) is the permutation induced by that on the columns, _, P(g) N Q(g) Then the row space (over C) =N • and the column space (over C) of decompos:e into isomorphic irreducible representation modules of Proof: on the g A of size There exist square matrices rn , and N G. B of size n , such that A- I NB --- [QI "" 00] So Let -1 A-I P(g) ~ AA _, NBB Q(g) B = p._ where -1 r is the rank of N B. A -· P(g) A, B- 1 : [p (g), II t:· :] QI (g) :::. [Q~ (g), ·~ (g)J ::. Q 11 (g) e P 11 (g) 11..(g)] . Q2..,,_(g) Q So Q(g) B , Q P'2-,(g), Then N. and P, (g) [:· :] f P., (g), Pz, (g)' Q,2(g).:::.O, ' :] P<I (g) :::: O, for all g <:= G. Hence the row and column spaces decompose into the same irreducibles. (89) Now consider ~, acting on the rows and the columns. in the representation module of Since the row space is contained s2""' on the 1-factors, any irreducible scrr) of N must correspond to a partition 11 of I::.,""' constituent 2m On the other hand, the column space is a submodule of into even parts. the representation of S2 ""'- on = (2 t , 2m - 2 t), i.e. where / s 2"""' It satisfies the conditions of the lemma, with NL ...... • M(,v.) (the set of tableaux of typer), 2m =2m - 2t + 2 + . . • . . + 2 . '--v--' t times. We prove the follo wing; Theorem: Let Tl= 2V into even parts. Tr ~(2t,2m - 2t) and be a partition of S trr) S row(Nt """) , col (Nt- Ynen J Proof: ' 2m J . Vle proceed in exactly the same manner as in the proof of Theorem C. Let T be a tableau corresponding to the partition Ti: 'ii,"" ... .:tTil< , 1T1 ~2m where Let the first - 2t, S S:. R and v(T) =- 1T-~2 I for all i > 1. be the subgroup that acts as the symmetric group on 2m - 2t We define and positions in the first row of the tableau. u(T) as in Theorem c, 2_ u(T). s .. SE. S Now v(T) occurs as a vector in the row space of Nl- 0\11. ' since it ~ is the characteristic vector of the set of 1-factors containing the t disjoint edges of 2m - 2t positions of u(T) which do not contain the letters in the first T. Again consider the coefficient of u(T) in v(T).f(T), namely, (90) sg(c) ceC,r!:R u ( T) • er ~ u ( T) • S If u ( T) • er : u ( T) • s So wT (u ( T) • c ) : wT( u ( T) ) = 1, Hen ce for u(T) .c -::. u(T). sr- 1 s €. s, then u(T).c =u(T).sr·I . = u(T), and the remainder of the argument follows exactly as before. We have shown that N.c, .... s;; span row ~ E(2n) f TT,~m-t. Note: Thompson proves this for the case m = 6, Let us look at the case i.e. t ~2, the but not by this me~~od. 1-factors of The K 1 ~. Ai 1 s can be arranged in order depending on the number of edges that two 1-factors have in common. in which they first appear in The Ei's row( Nt -,, """). can be arranged in the order We have (1 b) [12] (2,1'+-) g.o, 2] 1 (3,1 ) [s, 4] , [s, 2t.] (4,12.), ( 2'3-,1z. ) [6, 6] ' [6 ' 4' 2] ' [6' 2 (5,1), (2,3,1) [ 4 ]' 3 2, 2 '] , [ 4 ' 2 Cf] (6), (4 ,2), (3 1 ), (2"!l). [ 2"] . [4 1 J (91) These 1-factor schemes are not metric in tbe sense of Delsarte, but they bear a strong resemblance to the Johnson scheme, in that it is possible to define a generalised metric on the that two 1-factors are at distance common. One small difficulty arises in that there is no distance However if d for any three i 1-factors, by saying · if they have n - i edges in 1. denotes the distance function, then 1-factors From what we have just seen there is a similar partial order on the "!<'..IS ~ l • (8) Particular Examples, and Applications. (a) 1-factors arising from an oval of In such a case n n + 2 points in must be even, and to each of the outside the oval there corresponds a 1-factor of Kl"l-t2 , PG(2,n). n - 1 points determined by the intersections of the lines through that point with the oval, (see Thompson (29) ). This set Y of 1-factors of K~ 2 has the property that no two of them have mo~e tha..~ one edge in common, (for if they did, they would correspond to the same exterior point), and so with respect to certain relations. edges is contained in a unique Y is a clique Furthermore any pair of disjoint 1-factor. and we have, for the characteristic vector Therefore </Jy of Y; Y is a 2-design, (92) This gives three equalities in Delsarte•s inequalities for the distribution vector. However the otber inequalities are not very strong in this case. n1 One can also define two partial geometries on the set of 1 - exterior points depending on whether or not they lie on a secant or an exterior line of the oval. get a Let us consider the case n ~ 10. partial geometry the dual of ~hich is an (5,11,5) It has been shown that a projective p1ane of order 10 Then vrn 8(2,11,45). has no automorphisms apart from the identity. Suppose we have an oval in the plane. possible for the set of 99 a permutation which fixe s t he set as a whole. was. g ~ S 1'l. 1-factors arising from this oval, t here is Then the block graph of the But if g Is it S(2,ll,45) would have an automorphism. permutes the lines among themselves, then to an automorphism of the plane. Otherwise Euppose it. g g could be exter:ided would have to map the lines of the block graph to another set of geometrising cliques. But we have shown in 1-factors III(ll) that none exist. So this set of 99 has no nontrivial automorphisms. (b) 1-factorisations. A 1-factorisation of K is a set of 2n - 1 such that any edge lies in exactly one of them. for which relations between 1-factors of Cameron (4) K ~ 2 has asked 1-factors is it possible to construct a 1-factorisation such that any two of the 1-factors are related in the same way, and he gives a list of the known cases. A 1-factorisation of this t ype can be considered a s a clique id th respect to this relation. The figures we have calculated add only a little to what was already (93) (c) A8 and lGS 1-factors of A proof of the isomorphism of PSL(4,2) using the techniques of this thesis. We consider the graph on the to the relation (2,2), i.e. any two K, corresponding 1-factors are adjacent if they lie as follows, D D Then, from the P-matrix we obtain that : th.e · adj~cency matrix has least eigenvalue and has constant line sums. -2 theory of such graphs, fully recorded in line graph of ~ome graph. Furthermore We can apply the considerable (3), to obtain that G has the same parameters as the flag graph of a symmetric design with parameters is the flag graph of such a design. G is th e G has (15,7,3), and so 3G cliques of size corresponding to the points and blocks of this design. 7, These must be 1-factorisations such that the relations between the seven constituent 1-factors are all (2,2). These are the only such sir.ca the flag graph has only these parallel classes of AG(3,2) 30 give such a 1-factorisations cliques of size seven. 1-factorisation, and this has 8.7.6.4 30 Ag has two orbits of size There are 35 partitions of partition we can associate nine in the same orbit of A~, Therefore s8 is transitive on these automorphism group of size 1-factorisations, and 8 The 15. into two lots of 4. To any such 1-factors, and three of our 1-factorisations these being (94) <:. t,. <Zt7Jp P'I ,<~ ~a. ~~~ ~~l,,. l~l ol J;>Q: a...~ tr e-----f' c c [_./~~ <.. ~c\ ' :j t><l - - --- k In this way we obtain a set of 35 triples on the in an orbit of common. A • The triples have And so we have an S(2,3,15) 0 or 1 (hgf) under (hfg) 15 1-factorisations l~factorisation on one orbit, and the same (corresponding to the· same 35 it is doubly geometrisable. Hence it is projective A under 8(2,3,15) partitions) on the other orbit. And so 5-space over acts as a simpl~ group of automorphisms on it and, orders we see it must equal in PSL(4,2). GF(2). by comparing (95) References. (0) N.L.Biggs and A.T.White, Permutation Groups and Combinatorial Structures, London Mathematical Society Lecture Note Series, 33, Cambridge University Press. (1) R.C.Bose, Strongly regular graphs, partial geometries, and partially balanced designs, Pacific J. Math., 13 (1963), 389-419. (2) R.H.Bruck, Finite nets II. Uniqueness and imbedding, Pacific J. Math., 13 (1963), 421-457. (3) P.J.Cameron, J.M.Goethals, J.J.Seidel, and E.E.Shult, Line graphs, root systems, and elliptic geometry, Journal of Algebra, 43 (1976) 305-327. (4) P.J.Cameron, Parallelisms of Complete Designs, London Mathematical Society Lecture Note Series, 19, Cambridge University Press. (5) P.J.Cameron and J.H.van Lint, Graphs, Codes, and Designs, London Mathematical Society Lecture Note Series, 43, Cambridge University Press. (6) C.W.Curtis and I.Reiner, Representation Theory Of Finite Groups and Associative Algebras, Interscience, New York, 1962. (7) P.Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports Supplements, (1973) no.10. (96) (8) R.H.F.Denniston, A Steiner system with a maximal arc, Ars Cornbinatoria, 9 (1980), 247-248. (9) R.H.F.Denniston, personal communication. (10) M.Deza, Une propriete extremale des plans projectifs finis dans une classe des codes equidistants, Discr. Math., 6 (1973), 343-352. (11) M.Deza, P.Erdos, P.Frankl, Intersection properties of systems of finite sets, Proc. London Math. Soc., (3) 36 (1978) 369-384. (12) P.Erdos, Chao Ko, R.Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2) 12 (1961) 313-320. (13) P.Frankl, The Erdos, Ko, Rado Theorem is true for n =ckt, Colloquia Mathematica Societatis Janos Bolyai, 18, Combinatorics, (eds. A.Hajnal and V.Sos), Keszthely (Hungary), 1976. (14) J.-M.Goethals and J.J.Seidel, Strongly regular graphs derived from combinatorial designs, Canad. J. Math., 22 (1970), 597-614. (15) W.Haemers, Eigenvalue Techniques in Design and Graph Theory, Tract 121, Math. Centru.rn, Amsterdam, 1980. (16) M.Hall Jr., Combinatorial Theory, Blaisdell, Vialtham, Mass. 1967. (97) (17) G.Higman, On the simple group of D.G.Higman and C.C.Sims, Ill. J. Math., 13 (1969) 74-80. (18) A.J.Hoffman, Eigenvalues of graphs, in Studies in Graph Theory, part II, (ed. D.R.Fulkerson), M.A.A. Studies in Math., 1975, 225-245. (19) N.Ito, (20) D. E.Littlewood, Tight 4-designs, Osaka J. Math., 12 (1975 ) , 493-522. The Theor-1 of Group Characters, Oxford University Press, 1950. (21) P.J.Lorimer, A class of block designs having the same parameters as the design of points and lines in a projective 3-space, Lecture Notes in Math., 403. Springer Verlag, (1974) 73-78. (22) W.H.Mills, Two new block designs, Utilitas Mathematica, Vol.7, (1975) 73-75. (23) Elizabeth J. Morgan, Arcs in block designs, Ars Combinatoria 4 (1977) 3-16. (24) A.Neumaier,· Regular cliques in graphs, and special l!-designs, in Finite Geometries and Designs, (eds. Cameron, Hirschfeld, Hughes), London Math. Soc. Lecture Note Series(49), Cambridge University Press, 1981. (98) (25) D.K.Ray-Chaudhuri and R.M. Wilson, On t-designs, Osaka J. Math., 12 (1975) 757-7 44. (26) B. M.I. Hands, .An extension of the Erdos, Ko, Rado t heorem to t-designs, to appear, Journal of Combinatorial Theory, Series A. (27) J . Saxl, On multiplicity-free permuta tion r epresentations, in Finite Geometries and Designs, (eds. Cameron, Hirschfeld, Hughes ) , L. M.S. Lecture Note Seri es (49), Cambridge University Pre ss, 1981. (28 ) M. Smith, Doctoral Thesis, Mathematics Institute, University of Oxford, 1969. (29) J.G.Thompson, Fixed point free involutions and finite projective planes, in Finite Simple Groups II, ed. M.Collins, Academic Press, London, 1980. (30) H. Viielandt, Finite Permutation Groups, Academic Press, N. Y., 1964. (31) R.M. Wilson, Lecture Course in Combina torics, Caltech (1980-1981 ) .