Relation algebras and vertex conditions in graph theory
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Abstract
An association scheme (Q,[Gamma]), comprising a certain kind of partition [Gamma] of the direct square of a finite, nonempty set Q, corresponds to a binary relation algebra. A superscheme (Q,[Gamma]*) comprises a certain family of partitions of the direct powers Q[superscript n]+2 for each natural number n. Superschemes correspond to Krasner (relation) algebras. J.D.H. Smith showed that an association scheme (Q,[Gamma]) can be extended to a superscheme (Q,[Gamma]'*) if and only if it is a permutation group scheme, i.e. there exists a transitive, multiplicity-free permutation group G acting on Q such that each partition [Gamma superscript n] of the superscheme is the set of orbits of G acting componentwise on Q[superscript n]+2. A natural question arises: what prevents an association scheme from being built up any further to a superscheme beyond the partition [Gamma superscript t]?;A scheme can be associated with a graph. This scheme is an association scheme if and only if the graph is strongly regular. A height t presuperscheme consists of the bottom t levels of a superscheme. The dissertation contains a construction of a presuperscheme associated with a graph. The main theorem shows that if a presuperscheme associated with a graph is of height t, then the graph satisfies the (t + 3)-vertex condition. Shrikhande's graph provides an example of a scheme that cannot be extended beyond the bottom level. Then the generalization of this result is discussed. A similar construction of a presuperscheme associated with a colored, directed graph is given. If the scheme associated with a colored directed graph is an association scheme, the graph is strongly regular.;The main theorem shows that if a presuperscheme associated with a colored, directed graph is of height t, then the graph satisfies the (t + 3)-vertex condition. The reverse conclusion of the main theorem does not hold. We give an example of a colored, directed graph which satisfies the 4-vertex condition, but whose presuperscheme cannot be extended beyond the bottom (0-th) level. In particular, the example exhibits an association scheme that cannot be extended to a presuperscheme of positive height.