Covers And Quotients Of Symmetric Graphs

This thesis mainly focuses on the algebraic methods used to study symmetric graphs.Basic group action theory,mainly talks about the primitivity,is introduced in this thesis.The O'[Nan-Scott Theorem,which is about the characterization of finite primitive per-mutation groups,is the first main theorem about group actions.The affine type case is discussed detailedly which is used to construct some special graphs.Classical groups are important objects in finite group theory,some basic concepts such as projective space and projective linear group are shown in the thesis.The simplicity of PSL?n,q?for n>2 or|g|>3 can deduce that GL?n,q?is not soluble in the same case.And this result is used for proving some results in graph theory and group theory.Transitivity and primitivity of graphs are very interesting properties of symmetric graphs.This thesis introduces the Gert Sabidussi's construction for symmetric graphs by groups and cosets which are called coset graphs.The equivalence between coset graphs and symmetric graphs makes mathe-maticians enable to deal with groups instead of dealing with graphs,and this construction is used frequently in the thesis.The study of relations between covers and quotients is the main course of this thesis.Some conditions to determine whether a graph is a cover or a pseudo-cover of its quotient are given.The graph ?=Cos?????is a cover of the quotient graph ?=Cos?G,H,HgH?with conditions val?T?=val?E?and G>H>L is equivalent to every of the following condition:1.L acts transitively on[H:H?Hg];2.H=L?H?H^g?;3.L?Lg=L?H^g=H?L^g.This theorem is a guidance for researchers to check if a graph is a cover or a pseudo-cover of its quotient.For a special case that the quotient is a complete graph,this thesis also gives some examples that the original graph is a pseudo-cover.Even if the group,which determines the quotient,is soluble,we still can find an example due to the classical group construction.Fortunately,by Huppert's theorem of soluble 2-transitive groups,I prove that if the group is soluble with degree pn such that p is an odd prime,n>2 and pn?32,and also acts faithfully on the quotient,then the graph is the cover of its quotient with same valency.As the concept of group was established by Galois in the 19-th century,abstract al-gebra became one of the most important mathematical tools in researches.Graph theory is even an older topic for mathematicians that the paper written by Leonhard Euler on the Seven Bridges of Konigsberg and published in 1736 is regarded as the first paper in the history of graph theory.Some mathematicians realized the relations between the graphs and the groups,since some of the famous graphs have some symmetries which will be found in the automorphism groups of the graphs.Therefore,researches on symmetric graphs by using algebraic methods become a big and important part of the graph theory,which is characterized into the subject algebraic graph theory.Group theory helps a lot with the constructions in graph theory,conversely due to some algebraic graph methods,group theory also develops fast.For example,there are many groups are defined when studying graphs,which help to the classification of finite simple groups.Many famous graphs are defined by algebraic methods like Cayley graphs.The Cayley graph is a construction of graphs by groups given by Cayley.If G is a group,then we can construct a graph Cay?G,S?where the vertices are elements in the group,S is a subset of group G,and the edges are defined in the following way:Let x and y be two elements in G and yx^-1 ? S then we say there is an edge start from x toy.There is a theorem saying that a vertex transitive graph ? is a Cayley graph if and only if there is a regular subgroup in its automorphism group.A Cayley graph is a vertex-transitive graph,and note that G acts on the vertex set by right multiplication transitively.Further,Gert Sabidussi constructed coset graphs whose definition is very similar to Cayley graph.Let G be a group,H be a subgroup of G and S be a subset of G,then the coset graph is Cos?G,H,HSH?where the vertex set is the right cosets[G:H],the edges are defined in the following way:Let Hx and Hy be two right cosets and yx^-1 ? HSH,then there is an edge start from Hx to Hy.If G also acts on the vertex set transitively by right multiplication,and there is a theorem saying that every arc-transitive graph is a coset graph and if the graph ? is a G-arc-transitive graph then ?=Cos?G,H,HgH?where g2 ? H.Before 1985,we can only find the list of vertex-transitive graphs of order at most 13 by H.P.Yap?excluding those of valency 5 on 12 vertices?,and the list of all vertex-transitive graphs of order at most 19 constructed by B.D.McKay by using matrices.The vertex-transitive graphs of orders n=20,21,22 and 23 were constructed by McKay and Royle.However,the method used to construct the previous graphs did not easily carry over to the case n=24.The enumeration of the vertex-transitive graphs of order 24 was completed by G.F.Royle and Praeger,which is required the classification of the transitive permutation groups of degree 12 with the help of the computers.It is very difficult to enumerate the vertex-transitive graphs,since the number of graphs is too large to store and it is difficult to test whether they are isomorphic.Since up to isomorphism,there are 7753 vertex-transitive graphs of order 24.McKay and Royle guessed Cayley graphs may be the major part of vertex-transitive graphs.And McKay and Praeger make a conjecture:For n?1,Let vtr?n?and cay?n?denote the numbers of isomorphism types of vertex-transitive graphs and Cayley graphs,respectively,with order at most n.Then???Arc-transitive graphs are also called symmetric graphs,and the properties of sym-metric graphs are related to groups with their actions.Many mathematicians study on group theory also do some researches about symmetric graphs.Quotient graphs inherit symmetry of the original graph and mathematicians cares how many properties does quo-tient graph exactly inherit.However,there are examples that the quotient graph is not 2-arc-transitive but the original graph is.Therefore,researchers start to consider covers.Cover is an important case when study quotients,since the properties such as s-arc-transitivity will be inherited by the quotient graph.So the study of relations between quotient and cover is a big topic in algebraic graph theory.Suppose G is an imprimitive group,the orbits of its normal subgroup N form a block system.If the quotient graph is defined by the orbits of a normal subgroup,we call it normal quotient.It can be easily proved that the locally primitive normal quotient deduces cover.If the valencies of two graphs are the same,then the normal quotient also deduces cover.Moreover,if any two conditions of locally primitive,normal quotient and equal valency hold,then the original graph is a cover of its quotient.So here comes a question:if two graphs have the same valency,what conditions can make the original graph become a cover of its quotient.This is the motivation and the main problem of this thesis.There are also many Chinese mathematicians focus on the quotient graphs:Sanming Zhou gave a classification of a family of symmetric graphs with complete 2-arc-transitive quotients in 2008;he also gave a classification of the case where there is exactly one edge of T between any two distinct blocks together with Teng Fang,XinGui Fang and Binzhou Xiain 2015.It is easy to see that the valency of the cover is equal to the valency of the quotient.In past many years,some mathematicians believe that if the valencies of two graphs are equal,then the relation will be cover.However,Caiheng Li gave a construction of quotient graph that the original graph is not a cover but the valency keeps the same:Let p???1?mod 16?be a prime and G=PSL?2,p?.H is a sylow-2 subgroup of G such that H=<a>???<b>?D16.Then<a⁴,b)>?Z₂² and NG??a⁴,b???S4.And there exists g ? NG??a⁴,b??such that g2=1 and bg=a⁴.Let L=?a⁴,ba??Z22,=and define?=Cos?G,H,HgH?,?=Cos?G?L?LgL?.This is a very meaningful topic,since cover is a very important researching topic in algebraic graph theory,which has some relations to the s-arc-transitive graphs.There are lots of researches on symmetric graphs and s-arc-transitive graphs from 20-th century to now.Many exciting results are given by many famous mathematicians.For s-transitive graphs,there is a beautiful result of W.T.Tutte in 1947,he proved that there exist no s-arc-transitive cubic graphs for s>6.Since then,the class of finite s-arc-transitive graphs have received considerable attention.One of the most remarkable results in the area is that there exist no s-arc-transitive graphs for s=6 and s?8,which was obtained by R.Weiss in 1981.Further,for each value of s ? {1,2,3,4,5,7} there exist s-arc-transitive graphs.In 2000,Caiheng Li proved that there exist no s-arc-transitive graphs of odd valency for s?4.The primitivity is an important property of transitive groups.The O'Nan-Scott Theo-rem,proved independently by Michael O'Nan and Leonard Scott in 1980,one of the most important and useful theorems for studying finite primitive permutation groups and their applications.The O'Nan-Scott Theorem provides an identification of several types of fi-nite primitive permutation groups.For each type,we have information about the abstract group theoretical structure and the nature of the action.With O'Nan-Scott Theorem,we can deal with primitive graphs,locally primitive graphs and multiple transitive groups.Praeger study the groups satisfying that every nontrivial normal subgroups are transitive.These groups are called quasiprimitive since the property of these groups are similar to primitive groups.The class of finite quasiprimitive permutation groups is also described in a similar way as the O'Nan-Scott Theorem,which is called O'Nan-Scott-Praeger The-orem.This theorem is very useful in describing the graphs with normal 2-arc-transitive quotients.To study soluble 2-transitive groups,Bertram Huppert classified transitive finite lin-ear groups.Therefore,I can deal with the case that a pseudo-cover with a complete quo-tient and a soluble automorphism group.With Huppert's work on 2-transitive soluble groups,many mathematicians devoted to the study of classification of 2-transitive groups.These researches may provide a further study for pseudo-cover with a complete quotient.The classical groups are an important part in the study of finite groups.A big class of finite simple groups are found in the classical groups.When studying the affine type of O'Nan-Scott Theorem,we have to consider linear groups.Therefore,we have to study some properties of classical groups for studying soluble 2-transitive groups.In fact,the properties of the generators of special linear groups and the simplicity of projective special linear groups are important parts in the proof of the non-existence of pseudo-cover if it has a complete quotient and a soluble automorphism group with degree unequal to 9.The MAGMA system gives an efficient tool for mathematicians to calculate with algebraic objects.In this thesis,some proofs are due to the powerful calculation ability of MAGMA,and some examples,which depend on some operations on concrete groups,is also done by this system.Since pseudo-cover is a new concept,some properties of pseudo-covers are not dis-covered.This thesis only provides some examples of pseudo-cover and some ways to find construct them.Many properties of pseudo-covers still hide behind the examples.The connection of pseudo-covers and other mathematical objects is also a direction for further study.