Automorphisms of random graphs with specified vertices
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.
- scientific article; zbMATH DE number 3906527 (Why is no real title available?)
- scientific article; zbMATH DE number 3773632 (Why is no real title available?)
- scientific article; zbMATH DE number 3600068 (Why is no real title available?)
- scientific article; zbMATH DE number 3604904 (Why is no real title available?)
- Numbers of cubic graphs
- The asymptotic number of labeled graphs with given degree sequences
- The asymptotic number of non-negative integer matrices with given row and column sums
- The Asymptotic Number of Unlabelled Regular Graphs
- The number of matchings in random regular graphs and bipartite graphs
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- The asymptotic number of claw-free cubic graphs.
- The genus of curve, pants and flip graphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- On compactness of logics that can express properties of symmetry or connectivity
- On the structure of random graphs with constant r-balls
- Random regular graphs of high degree
- Hamilton cycles containing randomly selected edges in random regular graphs
- ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE
- The automorphism group of random graphs with a given number of edges
- ASYMPTOTIC BEHAVIOR OF AUTOMORPHISMS OF GRAPHS
- scientific article; zbMATH DE number 3959461 (Why is no real title available?)
- On the asymmetry of random regular graphs and random graphs
- Constructing of orientable wicks forms and estimation of their number
- Random-link matching problems on random regular graphs
- Approximate lumpability for Markovian agent-based models using local symmetries
- The Threshold of Symmetry in Random Graphs with Specified Degree Sequences
- Statistics of Feynman amplitudes in \(\phi^4\)-theory
- Regular graphs with positive Ollivier-Ricci curvature
- Randomly twisted hypercubes: between structure and randomness
This page was built for publication: Automorphisms of random graphs with specified vertices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760705)
