Research work · 1998

Relation algebras and vertex conditions in graph theory

Jerzy Wojdyło

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.

DOI: 10.31274/rtd-180813-10749