Constructions Of Directed Strongly Regular Graphs And Association Schemes Based On Finite Geometries

The concept of a distance regular graph is one of the central objects in algebraic combinatorial theory. It corresponds to a special class of association schemes, and has close connections with finite geometries, combinatorial designs and coding theory. As the distance regular graphs of diameter 2, strongly regular graphs are also investigated by many scholars. As a generalization of strongly regular graphs, Duval defined the directed strongly regular graph in 1988. Dam and Omidi introduced the concept of strongly walk-regular graph in 2013, and generalized that to directed strongly walk-regular graph in 2015, which makes the strongly regular graph theory more deep and rich.In this dissertation, we mainly construct four classes of directed strongly regular graphs and a class of association schemes based on finite geometries. The union of three relation graphs of the association scheme is the complementary graph of the second class. We determine the parameters of the directed strongly regular graphs and the intersection numbers of the association scheme. The full automorphism groups of the first class of the graphs and the automorphism group of the association scheme are also given.Firstly, we construct directed strongly regular graphs I using the matrices of rank 1 over finite fields. For any n x n matrix over the finite field with q element, Fq, suppose [X]={tX|t ∈ Fq*}, and we write X for [X] in the following. We define the graph F(n, q) to be the directed graph with{X\X ∈Ffq(n×n)，r(X)=1,X2=0} as its vertex set. For any two points A and B, A â†' B if and only if AB≠0. Similarly, the graph T’(n, q) is the directed graph with{X|X ∈F(n×n)q,r(X)=1,X2≠0} as its vertex set and Aâ†' B if and only if AB= 0. Then both T(n,q) and T’(n, q) are directed strongly regular graphs. We determine the parameters and full automorphism groups, respectively.Secondly, we construct a finite incidence structure. Let P be the set of all s-flats in the n-dimensional projective space over Fq, which are called points. Let B be the set of all m-flats, which are called blocks, where 0≤s<m<n. We get the inci-dence structure T(s,m;n,q)= (P,B,E), where the incidence relation between points and blocks is defined to be the incidence relation of flats. We now define the graph â…¡ using the incidence structure T(s,m;n,q). The graph T(s,m;n,q) is the directed graph with{(X,Y) ∈ P×B | X ∈ Y} as its vertex set and (X1,Y1)â†' (X2,Y2) if and only if (X1, Y1) ≠ (X2, Y2) and X1 ∈ Y2. For any (s-1)-flat, K, we use F(s, m; n, q, K) to repre-sent the subgraph of F(s, m; n, q) induced by the set{(X, Y) ∈ VT(s, m; n,q)| K (?) X}. Then T(s,m;n,q) is a 11/2-design if and only if s= 0 or m= n-1. T(0,m;n,q), F(s, n-1; n, q) and F(s, m; n, q, K) are directed strongly regular graphs, and the param-eters of T(s, m; n, q, K) are independent with the choice of K.Thirdly, we obtain directed strongly regular graphs III and IV using the trace func-tion and the 1-dimensional subspaces, respectively.Finally, a class of association schemes are given by the ordered pair of 1-dimensional subspaces and 2-dimensional subspaces of the n-dimensional vector space over finite fields. Let Mm be the set of all m-dimensional vector subspaces of the n-dimensional space over the finite field Fq, where n≥4. Suppose X={(A,B)|A ∈ M1, B E M2, A (?) B}. The action of the generalized linear group of order n over Fq, GLn(Fq), on X, is transitive, and induces naturally an association scheme of class 6. The intersection numbers and the automorphism group are determined.