Analysing finite locally 𝑠-arc transitive graphs

Giudici, Michael; Li, Cai; Praeger, Cheryl

doi:10.1090/S0002-9947-03-03361-0

Analysing finite locally $s$-arc transitive graphs
HTML articles powered by AMS MathViewer

by Michael Giudici, Cai Heng Li and Cheryl E. Praeger PDF

Trans. Amer. Math. Soc. 356 (2004), 291-317 Request permission

Abstract:

We present a new approach to analysing finite graphs which admit a vertex intransitive group of automorphisms $G$ and are either locally $(G,s)$–arc transitive for $s \geq 2$ or $G$–locally primitive. Such graphs are bipartite with the two parts of the bipartition being the orbits of $G$. Given a normal subgroup $N$ which is intransitive on both parts of the bipartition, we show that taking quotients with respect to the orbits of $N$ preserves both local primitivity and local $s$–arc transitivity and leads us to study graphs where $G$ acts faithfully on both orbits and quasiprimitively on at least one. We determine the possible quasiprimitive types for $G$ in these two cases and give new constructions of examples for each possible type. The analysis raises several open problems which are discussed in the final section.

References

Robert W. Baddeley, Two-arc transitive graphs and twisted wreath products, J. Algebraic Combin. 2 (1993), no. 3, 215–237. MR 1235278, DOI 10.1023/A:1022447514654
I. Z. Bouwer and D. Ž. Djoković, On regular graphs. III, J. Combinatorial Theory Ser. B 14 (1973), 268–277. MR 316310, DOI 10.1016/0095-8956(73)90011-7
Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031, DOI 10.1017/CBO9780511623677
Marston D. Conder, Cai Heng Li, and Cheryl E. Praeger, On the Weiss conjecture for finite locally primitive graphs, Proc. Edinburgh Math. Soc. (2) 43 (2000), no. 1, 129–138. MR 1744704, DOI 10.1017/S0013091500020745
J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson, $\Bbb {ATLAS}$ of finite groups, Oxford University Press, Eynsham, 1985. Maximal subgroups and ordinary characters for simple groups; With computational assistance from J. G. Thackray. MR 827219
A. Delgado, D. Goldschmidt, and B. Stellmacher, Groups and graphs: new results and methods, DMV Seminar, vol. 6, Birkhäuser Verlag, Basel, 1985. With a preface by the authors and Bernd Fischer. MR 862622
P. Dembowski, Finite geometries, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Springer-Verlag, Berlin-New York, 1968. MR 0233275, DOI 10.1007/978-3-642-62012-6
Shao-Fei Du and Dragan Marušič, Biprimitive graphs of smallest order, J. Algebraic Combin. 9 (1999), no. 2, 151–156. MR 1679249, DOI 10.1023/A:1018625926088
Shaofei Du and Mingyao Xu, A classification of semisymmetric graphs of order $2pq$, Comm. Algebra 28 (2000), no. 6, 2685–2715. MR 1757424, DOI 10.1080/00927870008826987
Xin Gui Fang, Cai Heng Li, and Cheryl E. Praeger, On locally two–arc transitive graphs admitting a Ree simple group, in preparation.
Jon Folkman, Regular line-symmetric graphs, J. Combinatorial Theory 3 (1967), 215–232. MR 224498, DOI 10.1016/S0021-9800(67)80069-3
Michael Giudici, Cai Heng Li, and Cheryl E. Praeger, Characterising finite locally $s$–arc transitive graphs with a star normal quotient, in preparation.
—, Some locally 3–arc transitive graphs constructed from triality, submitted.
David M. Goldschmidt, Automorphisms of trivalent graphs, Ann. of Math. (2) 111 (1980), no. 2, 377–406. MR 569075, DOI 10.2307/1971203
A. A. Ivanov and M. E. Iofinova, Biprimitive cubic graphs, Investigations in the algebraic theory of combinatorial objects, Kluwer, 1993, pp. 459–472.
A. A. Ivanov and Cheryl E. Praeger, On finite affine $2$-arc transitive graphs, European J. Combin. 14 (1993), no. 5, 421–444. Algebraic combinatorics (Vladimir, 1991). MR 1241910, DOI 10.1006/eujc.1993.1047
Cai Heng Li, On finite moufang graphs, in preparation.
Cai Heng Li, Finite $s$-arc transitive graphs of prime-power order, Bull. London Math. Soc. 33 (2001), no. 2, 129–137. MR 1815416, DOI 10.1112/blms/33.2.129
Cai Heng Li, The finite vertex-primitive and vertex-biprimitive $s$-transitive graphs for $s\geq 4$, Trans. Amer. Math. Soc. 353 (2001), no. 9, 3511–3529. MR 1837245, DOI 10.1090/S0002-9947-01-02768-4
Cai Heng Li, Cheryl E. Praeger, Akshay Venkatesh, and Sanming Zhou, Finite locally-quasiprimitive graphs, Discrete Math. 246 (2002), no. 1-3, 197–218. Formal power series and algebraic combinatorics (Barcelona, 1999). MR 1887486, DOI 10.1016/S0012-365X(01)00258-8
Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, On the O’Nan-Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A 44 (1988), no. 3, 389–396. MR 929529, DOI 10.1017/S144678870003216X
Cheryl E. Praeger, On a reduction theorem for finite, bipartite $2$-arc-transitive graphs, Australas. J. Combin. 7 (1993), 21–36. MR 1211263
Cheryl E. Praeger, An O’Nan-Scott theorem for finite quasiprimitive permutation groups and an application to $2$-arc transitive graphs, J. London Math. Soc. (2) 47 (1993), no. 2, 227–239. MR 1207945, DOI 10.1112/jlms/s2-47.2.227
Cheryl E. Praeger, Finite quasiprimitive graphs, Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 65–85. MR 1477745, DOI 10.1017/CBO9780511662119.005
Gert Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438. MR 175815, DOI 10.1007/BF01304186
D. H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford Ser. (2) 22 (1971), 551–557. MR 327584, DOI 10.1093/qmath/22.4.551
Bernd Stellmacher, Locally $s$–transitive graphs, unpublished.
Michio Suzuki, Gun ron. Vol. 1, Gendai Sūgaku [Modern Mathematics], vol. 18, Iwanami Shoten, Tokyo, 1977 (Japanese). MR 514842
Garrett Birkhoff and Morgan Ward, A characterization of Boolean algebras, Ann. of Math. (2) 40 (1939), 609–610. MR 9, DOI 10.2307/1968945
W. T. Tutte, On the symmetry of cubic graphs, Canadian J. Math. 11 (1959), 621–624. MR 109794, DOI 10.4153/CJM-1959-057-2
R. Weiss, $s$-transitive graphs, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 827–847. MR 642075
Richard Weiss, The nonexistence of $8$-transitive graphs, Combinatorica 1 (1981), no. 3, 309–311. MR 637836, DOI 10.1007/BF02579337
Richard Weiss, Generalized polygons and $s$-transitive graphs, Finite geometries, buildings, and related topics (Pingree Park, CO, 1988) Oxford Sci. Publ., Oxford Univ. Press, New York, 1990, pp. 95–103. MR 1072158