## Some topics in combinatorial design theory and algebraic graph theory

Author
Fiala, Nick Christopher

Year
2002

Advisor
Seress, Akos

Abstract
This dissertation consists of three chapters, each one based upon papers by the author. Chapter 1 deals with a conjecture in combinatorial design theory and extremal set theory known as the λ-design conjecture. A λ-design on v points is a set of v subsets (blocks) of a v-set (points) such that any two distinct blocks meet in exactly λ points and not all of the blocks have the same size. Ryser's and Woodall's λ-design conjecture states that all λ-designs can be obtained from symmetric designs by a complementation procedure. We prove the conjecture is true when v = 6p + 1, where p is prime, and when v = 8 q + 1, where q ≡ 1 or 7 (mod 8) is prime. Chapter 2 deals with the determination of all strongly regular graphs (srg's) with chromatic number 5. A srg is a finite simple regular graph, not complete or edgeless, such that the number of common neighbors of any two distinct vertices depends only upon whether or not they are adjacent. The chromatic number of a graph is the fewest number of colors that are required to color its vertices such that adjacent vertices always receive different colors. Haemers determined all srg's with chromatic number 3 or 4. We use eigenvalue techniques and computer enumerations to begin the determination of all srg's with chromatic number 5. We show that there are at most 43 possible sets of parameters for such a graph. We deal completely with 32 sets and obtain a partial result for another set. Chapter 3 deals with a generalization of srg's the author calls strongly regular vertices (srv's) and partially strongly regular graphs (psrg's). A srv in a finite simple graph is such that the number of common neighbors it has with any other vertex depends only upon whether or not they are adjacent. A psrg is a regular graph with at least one srv. We prove some basic properties of srv's and psrg's, provide several constructions of psrg's, determine all psrg's on at most 10 vertices, and make several conjectures regarding psrg's.