Random strongly regular graphs?

Peter J. Cameron*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36,10,4,2), but there are 32548 non-isomorphic graphs with parameters (36,15,6,6). (The first assertion is a special case of a theorem of Shrikhande, while the second is the result of a computer search by McKay and Spence.) In the light of this, it will be difficult to develop a theory of random strongly regular graphs! For certain values of the parameters, we have at least one prerequisite for a theory of random objects: there should be very many of them (e.g. superexponentially many). Two other features we would like are a method to sample from the uniform distribution (this is known in a couple of special cases) and information about how various graph parameters behave as random variables on the uniform distribution. Very little is known but there are a few recent results and some interesting problems. This paper develops no general theory, but explores a few examples and techniques which can be applied in some cases. Thomason has developed a theory of "pseudo-random graphs" which he calls (p,α)-jumbled graphs. Some of these graphs are strongly regular, but they are very special strongly regular graphs. I conclude with some speculation about "random jumbled graphs".

Original languageEnglish
Pages (from-to)103-114
Number of pages12
JournalDiscrete Mathematics
Volume273
Issue number1-3
DOIs
Publication statusPublished - 11 Dec 2003

Keywords

  • Random graphs
  • Strongly regular graphs

Fingerprint

Dive into the research topics of 'Random strongly regular graphs?'. Together they form a unique fingerprint.

Cite this