# ALGEBRAIC COMBINATORICS

On highly regular strongly regular graphs
Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 843-878.

In this paper we unify several existing regularity conditions for graphs, including strong regularity, $k$-isoregularity, and the $t$-vertex condition. We develop an algebraic composition/decomposition theory of regularity conditions. Using our theoretical results we show that a family of non rank 3 graphs known to satisfy the $7$-vertex condition fulfills an even stronger condition, $\left(3,7\right)$-regularity (the notion is defined in the text). Derived from this family we obtain a new infinite family of non rank $3$ strongly regular graphs satisfying the $6$-vertex condition. This strengthens and generalizes previous results by Reichard.

Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.183
Classification: 05E30,  51E12
Keywords: Strongly regular graphs, invariants, $k$-isoregularity, $t$-vertex condition, partial quadrangles, generalized quadrangles, partial linear spaces
@article{ALCO_2021__4_5_843_0,
author = {Pech, Christian},
title = {On highly regular strongly regular graphs},
journal = {Algebraic Combinatorics},
pages = {843--878},
publisher = {MathOA foundation},
volume = {4},
number = {5},
year = {2021},
doi = {10.5802/alco.183},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.183/}
}
TY  - JOUR
AU  - Pech, Christian
TI  - On highly regular strongly regular graphs
JO  - Algebraic Combinatorics
PY  - 2021
DA  - 2021///
SP  - 843
EP  - 878
VL  - 4
IS  - 5
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.183/
UR  - https://doi.org/10.5802/alco.183
DO  - 10.5802/alco.183
LA  - en
ID  - ALCO_2021__4_5_843_0
ER  - 
Pech, Christian. On highly regular strongly regular graphs. Algebraic Combinatorics, Volume 4 (2021) no. 5, pp. 843-878. doi : 10.5802/alco.183. https://alco.centre-mersenne.org/articles/10.5802/alco.183/

[1] Bamberg, John; De Clerck, Frank; Durante, Nicola Intriguing sets in partial quadrangles, J. Combin. Des., Volume 19 (2011) no. 3, pp. 217-245 | Article | MR 2760039 | Zbl 1225.05247

[2] Bannai, Eiichi Maximal subgroups of low rank of finite symmetric and alternating groups, J. Fac. Sci. Univ. Tokyo Sect. IA Math., Volume 18 (1971/72), pp. 475-486 | MR 357559

[3] Borceux, Francis Handbook of Categorical Algebra (Vol. 1), Encyclopedia of Mathematics and its Applications, 50, Cambridge University Press, Cambridge, 1994, xvi+345 pages | MR 1291599

[4] Bose, Raj C. Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math., Volume 13 (1963), pp. 389-419 | MR 157909

[5] Bose, Raj C.; Shrikhande, Sharadchandra S. Geometric and pseudo-geometric graphs $\left({q}^{2}+1,\phantom{\rule{0.166667em}{0ex}}q+1,\phantom{\rule{0.166667em}{0ex}}1\right)$, J. Geom., Volume 2 (1972), pp. 75-94 | Article | MR 302468 | Zbl 0226.05124

[6] Brouwer, Andries E. Parameters of Strongly Regular Graphs (https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html)

[7] Brouwer, Andries E.; Ivanov, Andrei V.; Klin, Mikhail H. Some new strongly regular graphs, Combinatorica, Volume 9 (1989) no. 4, pp. 339-344 | Article | MR 1054010 | Zbl 0709.05040

[8] Buczak, J. M. J. Finite Group Theory (1980) (D.Phil. Thesis)

[9] Cameron, Peter J. Partial quadrangles, Quart. J. Math. Oxford Ser. (2), Volume 26 (1975), pp. 61-73 | Article | MR 366702 | Zbl 0301.05009

[10] Cameron, Peter J. $6$-transitive graphs, J. Combin. Theory Ser. B, Volume 28 (1980) no. 2, pp. 168-179 | Article | MR 572472 | Zbl 0451.05038

[11] Cameron, Peter J.; Goethals, Jean-Marie; Seidel, Johan J. Strongly regular graphs having strongly regular subconstituents, J. Algebra, Volume 55 (1978) no. 2, pp. 257-280 | Article | MR 523457 | Zbl 0444.05045

[12] Cossidente, Antonio Combinatorial structures in finite classical polar spaces, Surveys in combinatorics 2017 (London Math. Soc. Lecture Note Ser.), Volume 440, Cambridge Univ. Press, Cambridge, 2017, pp. 204-237 | MR 3728108

[13] Cossidente, Antonio; Penttila, Tim Hemisystems on the Hermitian surface, J. London Math. Soc. (2), Volume 72 (2005) no. 3, pp. 731-741 | Article | MR 2190334 | Zbl 1085.51013

[14] De Clerck, Frank; Van Maldeghem, Hendrik Some classes of rank $2$ geometries, Handbook of incidence geometry, North-Holland, Amsterdam, 1995, pp. 433-475 | Article | MR 1360725

[15] Evdokimov, Sergei; Ponomarenko, Ilia Separability number and Schurity number of coherent configurations, Electron. J. Combin., Volume 7 (2000), Paper no. R31, 33 pages | MR 1763969

[16] Faradžev, Igor A.; Klin, Mikhail H.; Muzichuk, Mikhail E. Cellular rings and groups of automorphisms of graphs, Investigations in algebraic theory of combinatorial objects (Math. Appl. (Soviet Ser.)), Volume 84, Kluwer Acad. Publ., Dordrecht, 1994, pp. 1-152 | Article | MR 1273366

[17] Fon-Der-Flaass, Dmitry G. New prolific constructions of strongly regular graphs, Adv. Geom., Volume 2 (2002) no. 3, pp. 301-306 | MR 1924761

[18] GAP – Groups, Algorithms, and Programming, Version 4.11.1 (2021) (https://www.gap-system.org)

[19] Gardiner, Anthony Homogeneous graphs, J. Combinatorial Theory Ser. B, Volume 20 (1976) no. 1, pp. 94-102 | Article | MR 419293 | Zbl 0327.05111

[20] Gavrilyuk, Alexander L.; Makhnev, Alexander A. On Krein graphs without triangles, Dokl. Math., Volume 72 (2005) no. 1, pp. 591-594 | Zbl 1126.05102

[21] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | Article | MR 1829620

[22] Gol’fand, Jakov Ju.; Klin, Mikhail H. On $k$-homogeneous graphs, Algorithmic studies in combinatorics (Russian), Nauka, Moscow, 1978, p. 76-85, 186 (errata insert) | MR 509886

[23] Harary, Frank Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969, ix+274 pages

[24] Hestenes, Marshall D.; Higman, Donald G. Rank $3$ groups and strongly regular graphs, Computers in algebra and number theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970) (SIAM-AMS Proc.), Volume IV, Amer. Math. Soc., Providence, R.I., 1971, pp. 141-159 | MR 0340088

[25] Higman, Donald G. Partial geometries, generalized quadrangles and strongly regular graphs, Atti del Convegno di Geometria Combinatoria e sue Applicazioni (Univ. Perugia, Perugia, 1970) (1971), pp. 263-293 | MR 0366698

[26] Higman, Donald G. Invariant relations, coherent configurations and generalized polygons, Combinatorics (Proc. Advanced Study Inst., Breukelen, 1974), Part 3: Combinatorial group theory (Math. Centre Tracts), Volume 57 (1974), pp. 27-43

[27] Ivanov, Alexander A.; Shpectorov, Sergey V. A characterization of the association schemes of Hermitian forms, J. Math. Soc. Japan, Volume 43 (1991) no. 1, pp. 25-48 | Article | MR 1082421 | Zbl 0755.05099

[28] Ivanov, Andrei V. Non-rank-$3$ strongly regular graphs with the $5$-vertex condition, Combinatorica, Volume 9 (1989) no. 3, pp. 255-260 | Article | MR 1030380 | Zbl 0706.05056

[29] Ivanov, Andrei V. Two families of strongly regular graphs with the $4$-vertex condition, Discrete Math., Volume 127 (1994) no. 1-3, pp. 221-242 Graph theory and applications (Hakone, 1990) | Article | MR 1273605 | Zbl 0796.05098

[30] Kantor, William M. Generalized quadrangles associated with ${G}_{2}\left(q\right)$, J. Combin. Theory Ser. A, Volume 29 (1980) no. 2, pp. 212-219 | Article | MR 583960 | Zbl 0465.51007

[31] Kantor, William M. Some generalized quadrangles with parameters ${q}^{2}$, $q$, Math. Z., Volume 192 (1986) no. 1, pp. 45-50 | Article | MR 835389 | Zbl 0592.51003

[32] Kantor, William M.; Liebler, Robert A. The rank $3$ permutation representations of the finite classical groups, Trans. Amer. Math. Soc., Volume 271 (1982) no. 1, pp. 1-71 | Article | MR 648077 | Zbl 0514.20033

[33] Kaski, Petteri; Khatirinejad, Mahdad; Östergård, Patric R. J. Steiner triple systems satisfying the 4-vertex condition, Des. Codes Cryptogr., Volume 62 (2012) no. 3, pp. 323-330 | Article | MR 2886282 | Zbl 1236.05034

[34] Klin, Mikhail; Kriger, Nimrod; Woldar, Andrew Classification of highly symmetrical translation loops of order $2p$, $p$ prime, Beitr. Algebra Geom., Volume 55 (2014) no. 1, pp. 253-276 | Article | MR 3167793 | Zbl 1298.20078

[35] Klin, Mikhail; Meszka, Mariusz; Reichard, Sven; Rosa, Alex The smallest non-rank 3 strongly regular graphs which satisfy the 4-vertex condition, Bayreuth. Math. Schr. (2005) no. 74, pp. 145-205 | MR 2220246

[36] Klin, Mikhail H.; Woldar, Andrew J. The strongly regular graph with parameters $\left(100,22,0,6\right)$: hidden history and beyond, Acta Univ. M. Belii Ser. Math., Volume 25 (2017), pp. 5-62 | MR 3730780

[37] Kováčiková, Kristína Induced Subgraphs in Strongly Regular Graphs (2015) (Dissertation Thesis)

[38] Kriger, Nimrod Investigation of Strongly Regular Graphs of Latin Square Type and Related Combinatorial Objects (2015) (D.Phil. Thesis)

[39] Liebeck, Martin W.; Saxl, Jan The finite primitive permutation groups of rank three, Bull. London Math. Soc., Volume 18 (1986) no. 2, pp. 165-172 | Article | MR 818821 | Zbl 0586.20003

[40] Mac Lane, Saunders Categories for the working mathematician, Graduate Texts in Mathematics, 5, Springer-Verlag, New York, 1998, xii+314 pages | MR 1712872

[41] Macpherson, Dugald A survey of homogeneous structures, Discrete Math., Volume 311 (2011) no. 15, pp. 1599-1634 | Article | MR 2800979 | Zbl 1238.03032

[42] McKay, Brendan D.; Piperno, Adolfo Practical graph isomorphism, II, J. Symbolic Comput., Volume 60 (2014), pp. 94-112 | Article | MR 3131381 | Zbl 1394.05079

[43] Muzychuk, Mikhail A generalization of Wallis-Fon-Der-Flaass construction of strongly regular graphs, J. Algebraic Combin., Volume 25 (2007) no. 2, pp. 169-187 | Article | MR 2310420 | Zbl 1111.05101

[44] Nešetřil, Jaroslav Amalgamation of graphs and its applications, Second International Conference on Combinatorial Mathematics (New York, 1978) (Ann. New York Acad. Sci.), Volume 319, New York Acad. Sci., New York, 1979, pp. 415-428 | MR 556052

[45] Pasechnik, Dmitrii V. Skew-symmetric association schemes with two classes and strongly regular graphs of type ${L}_{2n-1}\left(4n-1\right)$, Acta Appl. Math., Volume 29 (1992) no. 1-2, pp. 129-138 (Interactions between algebra and combinatorics) | Article | MR 1192836 | Zbl 0760.05095

[46] Payne, Stanley E. Collineations of the generalized quadrangles associated with $q$-clans, Combinatorics ’90 (Gaeta, 1990) (Ann. Discrete Math.), Volume 52, North-Holland, Amsterdam, 1992, pp. 449-461 | Article | MR 1195827

[47] Payne, Stanley E.; Thas, Joseph A. Finite generalized quadrangles, EMS Series of Lectures in Mathematics, European Mathematical Society (EMS), Zürich, 2009, xii+287 pages | Article | MR 2508121 | Zbl 1247.05047

[48] Pech, Christian; Pech, Maja On a family of highly regular graphs by Brouwer, Ivanov, and Klin, Discrete Math., Volume 342 (2019) no. 5, pp. 1361-1377 | Article | MR 3910494 | Zbl 1407.05253

[49] Reichard, Sven A criterion for the $t$-vertex condition of graphs, J. Combin. Theory Ser. A, Volume 90 (2000) no. 2, pp. 304-314 | Article | MR 1757279 | Zbl 0947.05088

[50] Reichard, Sven Computational and Theoretical Analysis of Coherent Configurations and Related Incidence Structures (2003) (Ph.D Thesis)

[51] Reichard, Sven Strongly regular graphs with the 7-vertex condition, J. Algebraic Combin., Volume 41 (2015) no. 3, pp. 817-842 | Article | MR 3328181 | Zbl 1314.05235

[52] Segre, Beniamino Forme e geometrie hermitiane, con particolare riguardo al caso finito, Ann. Mat. Pura Appl. (4), Volume 70 (1965), pp. 1-201 | Article | MR 213949 | Zbl 0146.16703

[53] Slater, Peter J. A classification of $4$-connected graphs, J. Combinatorial Theory Ser. B, Volume 17 (1974), pp. 281-298 | Article | MR 373943 | Zbl 0298.05136

[54] Soicher, Leonard H. GRAPE, GRaph Algorithms using PErmutation groups, Version 4.8.5 (2021) (Refereed GAP package), https://gap-packages.github.io/grape

[55] Tits, Jacques Sur la trialité et certains groupes qui s’en déduisent, Inst. Hautes Études Sci. Publ. Math. (1959) no. 2, pp. 13-60 | MR 1557095

[56] Tutte, William T. A theory of $3$-connected graphs, Nederl. Akad. Wetensch. Proc. Ser. A 64 = Indag. Math., Volume 23 (1961), pp. 441-455 | MR 0140094

[57] van Dam, Edwin R.; Martin, William J.; Muzychuk, Mikhail Uniformity in association schemes and coherent configurations: cometric Q-antipodal schemes and linked systems, J. Combin. Theory Ser. A, Volume 120 (2013) no. 7, pp. 1401-1439 | Article | MR 3092674 | Zbl 1314.05236

[58] Wallis, Walter D. Construction of strongly regular graphs using affine designs, Bull. Austral. Math. Soc., Volume 4 (1971), pp. 41-49 | Article | MR 276113 | Zbl 0203.30802

Cited by Sources: