Maximal Cliques in Graphs Associated with Combinatorial Systems

Author: Rands, Bruce Michael Ian

Year: 1982

Degree: Dissertation (Ph.D.)

Advisor: Wilson, Richard M.

Committee Members: Dilworth, Robert P.; Kechris, Alexander S.; Ryser, Herbert J.; Wales, David B.; Wilson, Richard M.

Option: Mathematics

DOI: 10.7907/e1b1-vd02

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.

Files