1-Factorizations of random regular graphs

It is shown that for each r ≥ 3, a random r-regular graph on 2n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2n vertices, as n → ∞. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almost sure in one sequence of spaces are almost sure in the other, and vice versa. The corresponding statement is also shown for bipartite graphs, and from this it is shown that a random r-regular simple digraph is almost surely strongly r-connected for all r ≥ 2. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 305–321 (1997)     

Isomorphic factorizations VII. Regular graphs and tournaments

It is shown using enumeration results that for r > 2t, almost all labeled r-regular graphs cannot be factorized into t ? 2 isomorphic subgraphs. However, no examples of such nonfactorizable graphs are known which satisfy the obvious divisibility condition that the number of edges is divisible by t. Similar observations hold for regular tournaments (t ? 2} and for r-regular digraphs (r > t ? 2).     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

On the chromatic number of random d-regular graphs

In this work we show that, for any fixed d, random d-regular graphs asymptotically almost surely can be coloured with k colours, where k is the smallest integer satisfying d<2(k−1)log(k−1). From previous lower bounds due to Molloy and Reed, this establishes the chromatic number to be asymptotically almost surely k−1 or k. If moreover d>(2k−3)log(k−1), then the value k−1 is discarded and thus the chromatic number is exactly determined. Hence we improve a recently announced result by Achlioptas and Moore in which the chromatic number was allowed to take the value k+1. Our proof applies the small subgraph conditioning method to the number of equitable k-colourings, where a colouring is equitable if the number of vertices of each colour is equal.     

Linear Arboricity and Linear k-Arboricity of Regular Graphs

 We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs. Received: December 21, 1998 Final version received: July 26, 1999     

Asymptotic enumeration by degree sequence of graphs with degreeso(n 1/2)

We determine the asymptotic number of labelled graphs with a given degree sequence for the case where the maximum degree iso(|E(G)|^1/3). The previously best enumeration, by the first author, required maximum degreeo(|E(G)|^1/4). In particular, ifk=o(n ^1/2), the number of regular graphs of degreek and ordern is asymptotically $$\frac{{(nk)!}}{{(nk/2)!2^{nk/2} (k!)^n }}\exp \left( { - \frac{{k^2 - 1}}{4} - \frac{{k^3 }}{{12n}} + 0\left( {k^2 /n} \right)} \right).$$ Under slightly stronger conditions, we also determine the asymptotic number of unlabelled graphs with a given degree sequence. The method used is a switching argument recently used by us to uniformly generate random graphs with given degree sequences.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.