A combinatorial approach to optimal designs.

Abstract

A typical problem in experimental design theory is to find a block design in a class that is optimal with respect to some criteria, which are usually convex functions of the Laplacian eigenvalues. Although this question has a statistical background, there are overlaps with graph and design theory: some of the optimality criteria correspond to graph properties and designs considered ‘nice’ by combinatorialists are often optimal. In this thesis we investigate this connection from a combinatorial point of view. We extend a result on optimality of some generalized polygons, in particular the generalized hexagon and octagon, to a third optimality criterion. The E-criterion is equivalent with the graph theoretical problem of maximizing the algebraic connectivity. We give a new upper bound for regular graphs and characterize a class of E-optimal regular graph designs (RGDs). We then study generalized hexagons as block designs and prove some properties of the eigenvalues of the designs in that class. Proceeding to higher-dimensional geometries, we look at projective spaces and find optimal designs among two-dimensional substructures. Some new properties of Grassmann graphs are proved. Stepping away from the background of geometries, we study graphs obtained from optimal graphs by deleting one or several edges. This chapter highlights the currently available methods to compare graphs on the A- and D-criteria. The last chapter is devoted to designs to which a number of blocks are added. Cheng showed that RGDs are A- and D-optimal if the number of blocks is large enough for which we give a bound and characterize the best RGDs in terms of their underlying graphs. We then present the results of an exhaustive computer search for optimal RGDs for up to 18 points. The search produced examples supporting several open conjectures.