Algorithms In Combinatorial Design Theory - Lagout

ALGORITHMS INCOMBINATORIAL DESIGN THEORY

NORTH-HOLLAND MATHEMAICS STUDIESAnnals of DiscreteMathematics(26)General Editor: bter L. HAMMERRutgers University, New Brunswick, NJ, U.S.A.Advisory EditorsC BERG6 Universit4de Paris, FranceM.A. HARRISON, University of California, Berkeley, CA, U.S.A.K KLEE, University of Washington, Seattle, WA, U.S.A.J -H. VAN LIN 6 CaliforniaInstituteof Technology,Pasadena, CA, c!S.A.G,-C.ROTA, Massachusetts Institute of Technology, Cambridge, MA, U.S.A.NORTH-HOLLAND -AMSTERDAM0NEW YORK0OXFORD114

ALGORITHMS INCOMBINATORIAL DESIGN THEORYedited byC. J. COLBOURN and M. J. COLBOURNDepartmentof Computer ScienceUniversityof STERDAMNEW YORKOXFORD

QElsevier SciencePublishersE.K, 1985All rights reserved. No part of thisJpublicationmay be reproduced, stored in a retrievalsystem,or transmitted, in any form or by any means, electronic, mechanical,photocopying, recording orotherwise, without thepriorpermission of the copyright owner.ISBN: 0444878025Publishers:ELSEVIER SCIENCE PUBLISHERS B.V.P.O. BOX 19911000 BZ AMSTERDAMTHE NETHERLANDSSole distributorsforthe U.S.A. and Canada:ELSEVIER SCIENCE PUBLISHING COMPANY, INC.52 VANDER BILT AVENUENEW YORK, N.Y. 10017USA.Lihrar? of Congrcrr Calaloging in Publication DalaMain entry under t i t l e :Algorithms in combinatorial &sign theory.(Annals of discrete mathematics ; 26) (Horth-Hollaudmathematics studies ; 114)Include6 bibliographies.1. Combinatorial dcrigns and conrigurations--Dataprocessing. 2. Algorithms. I. Colbourn, C. J.(Cbsrles J. ), 1953XI. Colbourn, W. J. (MarleneJones), 1953111. Series. IV. Series: Northd ma emat s studies * 114.&W225.Aik1&5111.b65-10371ISM 0-444-87802-5 (U.8.). .PRINTED IN THE NETHERLANDS

VPREFACERecent years have seen an explosive growth in research in combinatorics and graph theory.One primary factor in this rapid development has been the advent of computers, and theparallel study of practical and efficient algorithms. This volume represents an attempt tosample current research in one branch of combinatorics, namely combmatorial designtheory,which is algorithmicin nature.Combmatorial design theory is that branch of combinatorics which is concerned with theconstruction and analysis of regular f h t e configurations such as projective planes, Hadamard matrices, block designs, and the like. Historically, design theory has borrowed toolsfrom algebra, geometry and number theory to develop direct constructions of designs.o n s ,are in fact algorithmsThese are typically supplemented by recursive n s t t iwhichfor constructing larger designs from me smaller ones. This lent an algorithmic flavourto the construction of designs, even before the advent of powerful computers.Computers have had a definite and long-lastingimpact on research in combinatorial designtheory. Rimarily, the speed of present day computershas enabled researchers to constructmany designs whose discovery by hand would have been difficuit if not imposslile. Asecond important consequence has been the vastly improved capability for anu&sis ofdesigns. This includes the detection of isomorphism, and hence gives us a vehicle foraddressing enumeration questions. It a h includes the determination of various properties of designs; examples include resolvability, colouring, decomposition, and subdesigns.Although in principle all such properties are computable by hand, research on designs withadditional properties has burgeoned largely because of the availability of computationalassistance.Naturally, the computer alone is not a panacea. It is a well-known adage in design theorythat computational assistance enables one to solve one higher order (only) than could bedone by hand. This is a result of the “combinatorial explosion”, the massive growth ratein the size of many combinatorial problems. Thus, research has turned to the developmentof practical algorithms which exploit computational assistance to its best advantage. Thisbrings the substantial tools of computer science, particularly analysis of algorithms andcomputationalcomplexity, to bear.Current research on algorithms in combinatorial design theory is diverse. It spans the manyareas of design theory, and involves computer science at every level from low-level implementation to abstract complexity theory. This volume is not an effort to survey the fsldexhaustively; rather it is an effort to present a collection of papers which involve designsand akorithms in an interesting way.

viReficeIt is our intention to convey the f m conviction that combinatorial design theory andtheoretical computer science have much to contribute to each other, and that there is avast potential for continued research in the area. We would like to thank the contributorsto the volume for helping us to illustrate the connections between the two disciplines.All of the papers were thoroughly refereed; we sincerely thank the referees, who are alwaysthe "unsung heroes and heroines" in a venture such as this. Finally, we would like especially to thank Alex Rosa,for helping in all stages from inception to publication.Charles J. Cofbourn and Marlene Jones ColbournWaterloo, CanadaMarch 1985

PrefaceVA.E. BROUWER and A.M. COHEN, Computation of some parameters of Liegeometries1M.CARKEET and P. EADES, Performance of subset generating aorithms49C.J. COLBOURN, MJ. COLBOURN, and D.R. STINSON, The computationalcomplexity of fuding subdesigns m combinatorialdesigns59M.J. COLBOURN, Algorithmic aspects of combinatorialdesigns: a sulvey67J.E. DAWSON, Algorithms to find directed packings137J.H. DINITZ and W.D. WALLIS, Four orthogonal one-factorizationson tenpints143D.Z. DU, F.K.HWANG and G.W.RICHARDS, A problem of lines andintersectionswith an application to switching networks151P.B. GIBBONS, A census of orthogonal Steiner triple systems of order 15165M.J. GRANNELL and T.S. GRINS, Derived Steiner triple systems of order 15183H.-D.O.F. CRONAU, A sulvey of results on the number o f t - (v, k, A) designs209J.J. HARMS, Directing cyclic triple systems221A.V. IVANOV, Constructive enumeration of incidence systems227E.S. KRAMER, D.W. LEAVITT, and S.S. MAGLIVERAS, Constructionprocedures for tdesigns and the existence of new simple 6designs247R MATHON and A. ROSA, Tables of parameters of BIBDs with r 41 includingexistence, enumeration, and resolvability results275A. ROSA and S.A. VANSTONE, On the existence of strong Kirkman cubesof order 39 and block size 3309

viiiCbntentsD.R. STINSON, Hill-climbing algorithms for the constructionof combinatodal&signs321

Annals of Discrete Mathematics 26 ( 1985) 1-480 Elsevier Science Publishers B.V. (North-Holland)IComput,ationof Some Parameters of Lie GeometriesA.E. Brouwr and A.M.CohcnCentre for Mathematics and Computer ScienceKruislaan 4131098 SJ AmsterdamTHE N E T H E R L A M ) SAbstractIn this note we show how one may compute the parameters of a finite Liegeometry, and we give the results of such computations in the mostinteresting cases. We also prove a little lemma that is useful for showingthat thick finite buildings do not have quotients which are (1ocalIy) Titsgeometries of spherical type.1. IntroductionThe finite Lie geometries give rise to association schemes whose parametersarc closely related to corresponding parameters of their associated Weyl groups.Though the parameters of the most common Lie geometries (such as projectivespaces and polar spaces) are very well known, we have not come across areference containing a listing of the corresponding parameters for geometries ofExceptional Lie type. Clearly, for the combinatorial study of these geometriesthe knowledge of these parameters is indispensible. The theorem in this paperprovides a formula for those parameters of the asociation scheme that appearin the distance distribution diagram of the graph underlying the geometry. As aconsequence of the theorem, we obtain a simple proof that the conditions inlemma 5 of 121 are fulfilled for the collinearity graph of any finite Lie geometryof type A,,, D,,, or Em,6SmS8. (See remark 3 in section 4. The proof for theother spherical types, i.e. C,,F,,and C2is similar.) By means of the formula inthe theorem, we have computed the parameters of the Lie geometries in themost interesting open cases for diagrams with single bonds only (A,, and 0, arewell known, and are given as examples). The remaining cases follow similarly,but the complete listing of all parameters would take too much space.

2A. E, Brouwer and A.M. a h e n2. InfroduetSon to Geometrler (following TSts [lo])A geometry over a set A (the set of types) is a triple (r,*,t) where r is a set(the set of objects of the geometry), * is a symmetric relation on r (theincidence relation) and t is a mapping (the type mapping) from I' into A, suchthat for x, y r we have (t(x) t(y) & x*y) if and only if x y. (Anexample isprovided by the collection r of all (nonempty proper) subspaces of a finitedimensional projective space, with t: r 4 N , the rank function, and *symmetrized inclusion (i.e., x*y iff x C y or y C x).)Often we shall refer t o the geometry as I' rather than as (r,*,t).A flag is a collection of pairwise incident objects. The residue Res(F) of aflag F is the set of all objects incident to each element of F. Together with theappropriate restrictions of * and t, this set is again a geometry.The rank of a geometry is the cardinality of the set of types A. Thecorank of a:flag F is the cardinality of A\t(F). A geometry is connected if andonly if the (looped) graph (r,*)is connected. A geometry is reeidually connectedwhen for each flag of corank 1, Res(F) is nonempty, and for each flag of coranka t least 2, Res(F) is nonempty and connected.A (Buekenhout-Tile) diagram is a picture (graph) with a node for eachelement of A and with labelled edges. It describes in a compact way a set ofaxioms for a geometry I' with set of types A as follows: whenever an edge( d l d 2 ) is labelled with D, where D is a class of rank 2 geometries, then eachresidue of type {d,,d2} of r must be a member of D . (Notice that a residue oftype {d,,d,}iis the residue of a flag of type A\{d1,d2}.) In the following we needonly two classes of rank 2 geometries. The first is the class of all projectiveplanes, indicltted in the diagram by a plain edge. The second is the class of allgeneralized digons, that is, geometries with objects of two types such that eachobject of one'type is incident with every object of the other type. Generalizeddigons are indicated in the diagram by an invisible (i.e., absent) edge.For example, the diagramis an axiom system characterizing the geometry of points, lines, and planes ofprojective &space. Note that the residue of a l i e (i.e., the points on the l i eand the planes containing the line) is a generalized digon. Usually, one choosesone element of A and calls the objects of this type pointe. The residues of thistype are called linee. Thus lines are geometries of rank 1, but all that matters isthey constitute subsets of the point set. In the diagram the node correspondingto the points is encircled.

Some parameters of Lie geometries3As an example, the principle of duality in projective 3-space asserts theisomorphism of the geometriesGrassmannians are geometries like(Warning: points are objects of the geometry but lines are sets of points, andgiven a line, there need not be an object in the geometry incident with the sameset of points.)Let us write down some diagrams (with nodes labelled by the elements ofA) for later reference.1122n33n-2n-19'Eoo-ouo-o12345