## 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 language | English |
---|---|

Pages (from-to) | 103-114 |

Number of pages | 12 |

Journal | Discrete Mathematics |

Volume | 273 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 11 Dec 2003 |

## Keywords

- Random graphs
- Strongly regular graphs