Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On the Graphs of Hoffman-Singleton and Higman-Sims. | On the Graphs of Hoffman-Singleton and Higman-Sims Paul R. Hafner Department of Mathematics University of Auckland Auckland New Zealand hafner@ Submitted Mar 2 2004 Accepted Aug 27 2004 Published Nov 3 2004 MR Subject Classifications 05C62 05C25 05B25 51E10 51E26 Keywords Hoffman-Singleton graph Higman-Sims graph Higman-Sims group biaffine plane S 3 6 22 Abstract We propose a new elementary definition of the Higman-Sims graph in which the 100 vertices are parametrised with Z4 X Z5 X Z5 and adjacencies are described by linear and quadratic equations. This definition extends Robertson s pentagonpentagram definition of the Hoffman-Singleton graph and is obtained by studying maximum cocliques of the Hoffman-Singleton graph in Robertson s parametrisation. The new description is used to count the 704 Hoffman-Singleton subgraphs in the Higman-Sims graph and to describe the two orbits of the simple group HS on them including a description of the doubly transitive action of HS within the Higman-Sims graph. Numerous geometric connections are pointed out. As a by-product we also have a new construction of the Steiner system S 3 6 22 . 1 Introduction The Higman-Sims graph is the unique strongly regular graph whose parameters are 100 22 0 6 . it is a graph of order 100 regular of degree 22 it is triangle-free any two adjacent vertices have 0 common neighbours and any two non-adjacent vertices have exactly 6 neighbours in common. This graph made its first official appearance 23 in the context of the construction of the sporadic simple group HS which is a subgroup of index 2 in the automorphism group of the graph note Section 13 for a comment on the history . In this paper we provide a new and elementary construction of the Higman-Sims graph combining a geometric interpretation 16 of Robertson s pentagon-pentagram construction of the Hoffman-Singleton graph with the known construction of the Higman-Sims THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R77 1 .
