Automorphisms of random graphs with specified vertices (Q760705): Difference between revisions

The main theorem of this paper applies to a very wide class of probability distributions for random n-vertex graphs, and gives (quite technical) sufficient conditions for the existence of asymptotic (large n) bounds on the expected number T(n) of nontrivial automorphisms of a random n-vertex graph. By specializing this theorem in various ways and using known results, the authors are able to obtain asymptotic results on, for example: the proportions of simple k-regular graphs and of simple bipartite graphs which have no nontrivial automorphisms; the number of unlabelled simple graphs with precisely d(i) vertices of degree i for each i; and the proportion of unlabelled k-regular simple graphs that are k-connected. The main theorem applies to any probability distribution on any set of labelled graphs, with loops and multiple edges permitted, provided that for each n all the n-vertex graphs in the set have the same degree sequence [g(1),...,g(n)]. Here g(i) is the degree of vertex i. The bounds are given in terms of a function f(n) which is arbitrary except for a condition the authors call 'acceptability' that relates f to the probabilities of appearance of subgraphs in a graph chosen from the given distribution on the set. The (still quite general) specialization that produces the corollaries is the following: given integers n, m(1),m(2), g(1),...,g(n), and a partition P of \(\{\) 1,...,n\(\}\), consider the uniform probability distribution on the set of graphs on the vertex set \(\{\) 1,...,n\(\}\) with degree sequence g(1),...,g(n) such that the number of edges joining vertices u and v is at most m(1) if u and v are in the same cell of P, and at most m(2) if not. Acceptable functions f(n) are found for these distributions.