Corrections and addenda to "Random regular graphs"

                        Last update: July 28, 2008

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 P.282, 
below.) Friedman has since proved Alon's conjecture that the second largest 
eigenvalue of a random d-regular graph is a.a.s. at most sqrt(2d) + epsilon 
for all epsilon > 0.

P.249 In the bounds leading to equation (10), the  "unwanted loops" term should
be O(d^2n) instead of O(adn), and that for triple edges should be O(bd^2+d^3n) 
instead of O(bdn). Equation (10) is correct. [Corrections pointed out by 
Sang-June Lee.]

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.264 Conjecture 2.27 is false, and this was apparently pointed out by Bruce Reed 
some years ago. For example, take a random graph with 100n vertices of 
degree 3 and 3n vertices of degree 100. Half of the ends of edges are 
incident with vertices of degree 100, so aas about an eighth of the degree 3 
vertices, or about 12n, have all three neighbours of degree 100, so the 
graph is not hamiltonian.

The conjecture still makes sense if some reasonable upper bound is placed 
on D as a function of d. Probably the most interesting case is still d=3 and 
D=4.

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).) 
Add the condition that the number of such i is finite.

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"