1196Accesses
Summary
Following Kharaghani and Torabi [On a decomposition of complete graphs,Graphs Comb.,19 (2003), 519–526], we introduce new concepts of Siamese color graph, Siamese association scheme and Siamese Steiner design. With the aid of a computer, we determine all Siamese objects on 15 points, as well as hundreds on 40 points. As a generalization of accumulated observations, an infinite series of Siamese association schemes related to certain imprimitive actions of the groupsPSL(2,q2) is outlined. Special attention is paid to the spirit of computer-aided activity, namely to algorithms, technical data, successfulad hoc tricks, and computer-free interpretations of obtained results.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 20591
- Price includes VAT (Japan)
- Softcover Book
- JPY 25739
- Price includes VAT (Japan)
- Hardcover Book
- JPY 25739
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Bannai and T. Ito,Algebraic Combinatorics I. Association Schemes, Benjamin/Cummings, Menlo Park, 1984.
T. Beth, D. Jungnickel, and H. Lenz,Design Theory, Cambridge University Press, Cambridge, 1993.
A. Betten, A. Kerber, R. Laue, and A. Wasserman, Simple 8-designs with small parameters,Designs Codes Cryptogr.,15 (1998), 5–27.
A. Betten, M. Klin, R. Laue, and C. Pech,A Computer Approach to the Enumeration of Block Designs which are Invariant with Respect to a Prescribed Permutation Group, Preprint MATH-AL-13-1997 Technische Univesitität Dresden, 1–51, supplement 52–74, 1997.
A. Betten, M. Klin, R. Laue, and A. Wasserman, Graphicalt-designs via Kramer-Mesner matrices,Discrete Math.,197/198 (1999), 83–109.
A. Betten, R. Laue, and A. Wasserman, DISCRETA: A program system for the construction oft-designs with a prescribed automorphism group, University of Bayreuth, 1998,http://www.mathe2.uni-bayreuth.de/betten/DISCRETA/index.html.
N. L. Biggs, Distance-regular graphs with diameter three,Ann. Discrete Math.,15 (1982), 69–80.
A. E. Brouwer,http://www.win.tue.nl/~aeb/
A. E. Brouwer, A. M. Cohen, and A. Neumaier,Distance Regular Graphs, Springer-Verlag, Berlin, 1989.
A. E. Brouwer, J. H. Koolen, and M. H. Klin, A root graph that is locally the line graph of the Petersen graph,Discrete Math.,264 (2003), 13–24.
G. Butler, The transitive groups of degree fourteen and fifteen,J. Symbol. Comput.,16 (1993), 413–422.
P. J. Cameron,Permutation Groups, Cambridge University Press, Cambridge, 1999.
F. N. Cole, L. D. Cummings, and H. S. White, Complete classification of the triad systems of 15 elements,Proc. Nat. Acad. Sci. USA,3 (1919), 197–199.
J. H. Conway, A. Hulpke, and J. McKay, On transitive permutation groups,London Math. Soc. J. Comput. Math.,1 (1998), 1–8.
J. Degraer and K. Coolsaet, Classification of three-class association schemes using backtracking with dynamic variable ordering,Discrete Math.,300 (2005), 71–81.
R. H. Dye, Maximal subgroups of symplectic groups stabilizing spreads II,Journal of London Math. Society (40),2 (1989), 215–226.
I. A. Faradžev and M. H. Klin, Computer package for computations with coherent configurations, in S. M. Wat (ed.)Proceedings ISSAC-91 Bonn, pp. 219–223, Assoc. Comput. Math. Press, New York, 1991.
I. A. Faradžev, M. H. Klin, and M. E. Muzichuk, Cellular rings and groups of automorphisms of graphs, in I. A. Faradžev, A. A. Ivanov, M. H. Klin and A. J. Woldar (eds.)Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications, Vol. 84, pp. 1–152, Kluwer Academic, Dordrecht, 1994.
R. A. Fisher, An examination of the different possible solutions of a problem in incomplete blocks,Ann. Eugenics,10 (1940), 52–75.
D. E. Flesner, The geometry of subgroups ofPSp4(2n),Illinois J. Math.,19 (1975), 42–70.
P. B. Gibbons and R. Mathon, Construction methods for Bhaskar Rao and related designs,J. Austral. Math. Soc., Ser. A,42 (1987), 5–30.
C. D. Godsil and A. D. Hensel, Distance regular covers of complete graphs,J. Comb. Theory, Ser. B,36 (1992), 205–238.
Ja. Ju. Gol’fand, A. V. Ivanov, and M. H. Klin, Amorphic cellular rings, in I. A. Faradžev, A. A. Ivanov, M. H. Klin, and A. J. Woldar (eds.)Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications, Vol. 84, pp. 167–186, Kluwer Academic, Dordrecht, 1994. Translated from Russian.
M. J. Grannel, T. S. Griggs, and J. P. Murphy, Equivalence classes of Steiner triple systems,Congressus Numerantum,86 (1992), 19–25.
M. Greig and A. Rosa, Maximal arcs in Steiner systems S(2,4,v). Combinatorics 2000 (Gaeta),Discrete Math. (1–3),267 (2003), 143–151.
J. L. Gross and T. W. Tucker,Topological Graph Theory, Dover, New York, 1987.
M. Hall and J. D. Swift, Determination of Steiner triple systems of order 15,Math. Tables Other Aids Comput.,9 (1955), 146–152.
F. Harary,Graph Theory, Addison–Wesley, Reading, 1969.
D. G. Higman, Coherent configurations,I. Rend. Sem. Mat. Univ. Padova,44 (1970), 1–25.
J. W. P. Hirschfeld,Finite Projective Spaces of Three Dimensions, Oxford University Press, Oxford, 1985.
D. R. Hughes and F. C. Piper,Design Theory, Cambridge University Press, Cambridge, 1985.
Y. J. Ionin, A technique for constructing symmetric designs,Designs Codes Cryptogr.,14 (1998), 147–158.
A. A. Ivanov, Construction of some new automorphic graphs using computers, inAir Physics and Applied Mathematics (Moscow) MPhTI, pp. 144–146, 1981 (in Russian).
A. Kerber and R. Laue, Group actions, double cosets and homomorphisms: Unifying concepts for the constructive theory of discrete structures, in M. Hazewinkel, A. A. Ivanov, and A. J. Woldar (eds.)Algebra and Combinatorics: Interactions and Applications. Acta Applicandae Mathematicae, Vol. 52 (1–3), pp. 63–90, Kluwer Academic, Dordrecht, 1998.
H. Kharaghani and R. Torabi, On a decomposition of complete graphs,Graphs Comb.,19 (2003), 519–526.
M. H. Klin, M. Meszka, S. Reichard, A. Rosa, and E. Spence, The smallest non-rank 3 strongly regular graphs which satisfy the 4-vertex condition,Bayreuther Mathematische Schriften,74 (2005), 145–205.
M. Ch. Klin, R. Pöschel, and K. Rosenbaum,Angewandte Algebra, Vieweg, Braunschweig, 1988.
M. H. Klin and S. Reichard, Siamese association schemes in miniature: A link between generalized quadrangles, graphs and Steiner designs. Abstracts of AMS Meeting (Bloomington), 2003, 985-05-232.
M. H. Klin, R. Reichard, and A. J. Woldar, Siamese objects and their relation to color graphs, association schemes and Steiner designs,Bull. Belgian Math. Soc. (5),12 (2005), 845–857.
M. H. Klin, S. Reichard, and A. J. Woldar, Siamese association schemes and Siamese Steiner designs. I. Introduction (in preparation).
M. H. Klin, S. Reichard, and A. J. Woldar, Siamese association schemes and Siamese Steiner designs. II. Objects on 15 points (in preparation).
M. Klin, C. Rücker, G. Rücker, and G. Tinhofer, Algebraic combinatorics in mathematical chemistry. Methods and algorithms. I. Permutation groups and coherent (cellular) algebras.MATCH,40 (1999), 7–138.
E. S. Kramer and D. M. Mesner,t-Designs on hypergraphs,Discrete Math.,15 (1976), 263–296.
H. W. Kuhn, On imprimitive substitution groups,Am. J. Math.,26 (1904), 45–102.
R. Laue, Computing double coset representatives for the generation of solvable groups,Lect. Notes Comput. Sci.,144 (1982), 65–70.
E. N. Martin, On the imprimitive substitution groups of degree fifteen and the primitive substitution groups of degree eighteen,Am. J. Math.,23 (1901), 259–286.
R. Mathon, Lower bounds for Ramsey numbers and association schemes,J. Comb. Theory, Ser. B,42 (1987), 122–127.
R. A. Mathon, K. T. Phelps, and A. Rosa, Small Steiner triple systems and their properties,Ars Combinatoria,15 (1983), 3–110.
B. D. McKay, nauty User’s Guide (Version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.
S. Milici, A. Rosa, and V. Voloshin, Colouring Steiner systems with specified block colour patterns,Discrete Math. (1–3),240 (2001), 145–160.
E. H. Moore, Tactical memoranda I–III,Am. J. Math.,18 (1896), 264–303.
S. E. Payne, All generalized quadrangles of order 3 are known,J. Comb. Theory,18 (1975), 203–206.
S. E. Payne, Tight point sets in finite generalized quadrangles,Congressus Numerantium,60 (1987), 243–260.
S. E. Payne, and J. A. Thas,Finite Generalized Quadrangles, Research Notes in Mathematics, Pitman, London, 1984.
S. Reichard, Computational and Theoretical Analysis of Coherent Configurations and Related Incidence Structures, Thesis, University of Delaware, Newark, 2003.
R. Remak, Über Untergruppen direkter Produkte von drei Faktoren,Crelle’s J. Reine Angewandte Math.,166 (1931), 65–100.
B. Schmalz,t-Designs zu vorgegebener Automorphismengruppe, Thesis, Universität Bayreuth,Bayreuther Mathematische Schriften,41 (1992), 1–164.
B. Schmalz, Thet-designs with prescribed automorphism group, new simple 6-designs,J. Comb. Des.,1 (1993), 126–170.
M. Schönert et al., GAPs – Groups, Algorithms, and Programming, Lehrstuhl D für Mathematik, Rheinisch-Westfälische Technische Hochschule, Aachen, 1995.
W. R. Scott,Group Theory, Dover, New York, 1987.
M. W. Short,The Primitive Soluble Permutation Groups of Degree Less than 256, Lecture Notes in Mathematics, Vol. 1519, Springer, Berlin, 1992.
L. H. Soicher, GRAPE: A system for computing with graphs and groups, in L. Finkelstein and W. M. Kantor (eds.)Groups and Computation, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 11, pp. 287–291, Amer. Math. Soc., Providence, 1993.
E. Spence,http://www.maths.gla.ac.uk/~es/srgraphs.html.
J. J. Sylvester, Elementary researches in the analysis of combinatorial aggregation,Philos. Mag.,24 (1844), 285–296.
J. A. Thas and S. E. Payne, Spreads and ovoids in finite generalized quadrangles,Geometrica Dedicata,52 (1994), 227–253.
J. A. Todd, As it might have been,Bull. London Math. Soc.,2 (1970), 1–4.
A. Wasserman, Finding simplet-designs with enumeration techniques,J. Comb. Des. (2),6 (1998), 79–90.
Author information
Authors and Affiliations
Ben-Gurion University of the Negev, Beer Sheva, 84105, Israel
Mikhail Klin
University of Western Australia, Crawley, 6009, Western Australia
Sven Reichard
Villanova University, Villanova, PA, 19085, USA
Andrew Woldar
- Mikhail Klin
You can also search for this author inPubMed Google Scholar
- Sven Reichard
You can also search for this author inPubMed Google Scholar
- Andrew Woldar
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toMikhail Klin.
Editor information
Editors and Affiliations
Department of Mathematics, Ben-Gurion University of the Negev, POB 653, 84633, Beer Sheva, Israel
Mikhail Klin
School of Mathematics, University of Southampton, Southampton, SO17 1BJ, UK
Gareth A. Jones
Faculty of Computer Science, Laboratory for Cryptography and Computer Security, Tržaška cesta 25, 1000, Ljubljana, Slovenia
Aleksandar Jurišić
Department of Mathematics and Computer Science, Netanya Academic College, University st. 1, 42 365, Netanya, Israel
Mikhail Muzychuk
V.A. Steklov Mathematical Institute, Laboratory of Representation Theory and Computational Mathematics, Fontanka 27, 191023, St. Petersburg, Russia
Ilia Ponomarenko
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Klin, M., Reichard, S., Woldar, A. (2009). Siamese Combinatorial Objects via Computer Algebra Experimentation. In: Klin, M., Jones, G.A., Jurišić, A., Muzychuk, M., Ponomarenko, I. (eds) Algorithmic Algebraic Combinatorics and Gröbner Bases. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01960-9_2
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-01959-3
Online ISBN:978-3-642-01960-9
eBook Packages:Mathematics and StatisticsMathematics and Statistics (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative