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.

Thesis Files