Corrections and addenda to "Random regular graphs"

                        Last update: May 22, 2003

P.248 Friedman's result referred to was not in the uniform model of random
regular graphs, but in the model derived from random permutation digraphs 
described in the last paragraph on P.282. (See the addendum to this page, 
below.)

P.251 Conjecture 2.11 has been proved by combining the results of 
C. Cooper, A. Frieze and B. Reed, Random regular graphs of
non-constant degree (manuscript), and M. Krivelevich, B. Sudakov, V. Vu and 
N.C. Wormald, Random regular graphs of high degree,  Random Structures and 
Algorithms (2001).


P.253 Theorem 2.13 on diameter is for every fixed d at least 3 and every
fixed epsilon > 0.

P.260 seven lines above the "Chromatic number" section:
The constant 0.2746 should be replaced by 0.2794 (with reference to
dominating sets). 
Next line: same correction.

Note: those corrected upper bounds also apply to independent dominating
sets.

P.260 Delete the last paragraph before the "Chromatic number" section
since stronger results on star forests come immediately from the
results on dominating sets. (A star forest with k edges corresponds
to a dominating set with n-k vertices, the vertices in the dominating
set being the centres of the stars.)

P.267 in Section 3.5, each s should be r and in the last four lines each r
should be d. Also G_{n,d,r} should be defined as a random d-regular 
r-uniform hypergraph on n vertices.

P.270 in Thm 4.1 and 4 lines after, and P. 271 in Cor. 4.2, and on P.
276: 
Each occurrence of Y subscript n should simply be Y.

P.270 In Theorem 4.1. Delete the final condition from Thm 4.1 that the sum
of lambda i (delta_i=-1) is finite. (This is implied by (c).) 

P.270 In Theorem 4.1. Add the condition to the first part
of the conclusion, that the variable $Y$ must equal 0 whenever $X_i>0$ for 
any $i$ such that $\delta_i=-1$. (Or equivalently, strengthen the
convergence in (b), in the case of convergence to 0, to require equality
with 0 for $n$ sufficiently large.)

P.273  2nd last line of proof of Thm 4.5. Write $X_2=0$ in place of $X_2>0$.

P.278 Start of Section 4.3. In the definition of superposition of two
graphs, it is intended that in the union of two graphs $G$ and $\hat G$, 
the multiplicity of an edge is the sum of the multiplicities of that edge 
in the two graphs $G$ and $\hat G$.

P 281. Just after Conjecture 4.19. For the contiguity version, Y_n 
should be deleted from one side. On the other side, parentheses should be
inserted around Y_n.

P.282 Janson's conjectures on permutation digraphs have now been proved:
C.S. Greenhill, S. Janson, J. H. Kim, and
 N.C. Wormald, Permutation pseudographs and contiguity, preprint.

P.283 Conjecture 4.22 is only for fixed d at least 3.

P.292 reference [34]: The title should be changed to "Minimum dominating
sets in random cubic graphs: average case" 

P.292 reference [44]: The title should be changed to "On the independence 
and chromatic numbers of random regular graphs"