Computational and Theoretical Analysis of Coherent Configurations and Related Incidence Structure
Sven Reichard
2003
In this thesis we investigate coherent configurations and their relations to incidence structures and diagram geometries. Coherent configurations, as introduced by Higman [52], form a generalization of association schemes (see Bannai-Ito [3]), and as such are central to Algebraic combinatorics.
In particular, we consider the following applications: Graphs with the t-vertex condition; an interesting new class of association schemes, so called "Siamese schemes"; configurations arising from partial geometries, maximal arcs in projective spaces, and related geometries; and others.
The t-vertex condition was introduced by Hestenes and Higman [51] in order to give a combinatorial characterization of some properties of graphs related to rank 3 permutation groups ("rank 3 graphs"). This motivates the investigation of graphs which satisfy the t-vertex condition but which are not rank 3 graphs. We investigate the point graphs of generalized quadrangles. We show that they always satisty the 5-vertex condition. If the order of the generalized quadrangle is of the form (s, s2), they also satisfy the 6-vertex condition. This gives the first examples (in fact, an infinite series) of such graphs which are not rank 3 graphs.
Next, we consider Siamese color graphs, as introduced by Kharaghani and Torabi [60]. These are colorings of complete graphs which are related to distance regular graphs, Steiner systems and generalized quadrangles. In some cases they give rise to association schemes, which we call Siamese schemes. After developing axioms for these objects, we find that they impose strong restrictions on the possible parameters. We give a complete classification of these objects for small orders, as well as a construction of an infinite series of Siamese schemes. As a byproduct, we obtain several new combinatorial objects, such as Steiner systems and distance regular graphs.
Given an incidence structure, or, more generally, a diagram geometry, one can define a set of natural binary relations on the elements (points, lines, etc.). If these relations form a coherent configuration, we speak of a coherent incidence structure. As examples we consider partial geometries, and diagram geometries arising from maximal arcs in projective planes. This leads to a new approach to the computer-aided construction of projective planes of order n containing maximal k-arcs. Special attention is given to case n=12, k=3, since this is the smallest order for which the existence of a projective plane is still open
Weakly neighborly maps are studied in Discrete Geometry as extermal objects. Here, we consider them under an algebraic point of view. In particular we classify small weakly neighborly maps admitting a sharply transitive automorphism group.