The property in the title is well-known. I am trying to find an original reference to its first appearance in print. The 4th edition of Graphs & Digraphs by Chartrand and Lesniak lists this as Theorem 13.6 and says that it's a generalization of a result by Gilbert, but gives no further reference.
$\begingroup$
$\endgroup$
asked Dec 3, 2012 at 11:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
I think you will find it in Moon, J. W.; Moser, L. Almost all (0,1) matrices are primitive. Studia Sci. Math. Hungar. 1 (1966) 153–156. But I don't have time to visit the library to be sure and I don't see it online.
It is certainly in Burtin, Ju. D. Asymptotic estimates of the diameter and the independence and domination numbers of a random graph. (Russian) Dokl. Akad. Nauk SSSR 209 (1973), 765–768.
I guess the Gilbert mentioned is Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 (1959) 1141–1144. It isn't clear exactly why...
answered Dec 3, 2012 at 14:00
-
$\begingroup$ The introductory paragraph of a 1981 TAMS paper by Bollobas available at ams.org/journals/tran/1981-267-01/S0002-9947-1981-0621971-7/… supports the likely Moon-Moser origin. Also, an author search on "e.n. gilbert" at projecteuclid.org will produce his "Random Graphs" article. $\endgroup$ Commented Dec 3, 2012 at 17:57
-
$\begingroup$ I checked the Moon Moser paper, that is indeed your reference. I've emailed you a somewhat crappy but legible scan of the paper. $\endgroup$ Commented Dec 3, 2012 at 19:59
$\begingroup$
$\endgroup$
2
The result you asked about follows instantly from Fagin's proof of the zero-one law for finite graphs. He shows that all of Gaifman's extension axioms have asymptotic probability 1, and "diameter $\leq 2$" is essentially one of the extension axioms. Fagin's paper is "Probabilities on finite models" [J. Symbolic Logic 41 (1976) pp.50-58]. I believe the zero-one law was proved earlier by four Russians, but I don't have access to their paper and don't know whether their method immediately implies the "diameter $\leq2$" result.
answered Dec 3, 2012 at 13:48
-
$\begingroup$ The four Russians are Y.V. Glebskii, D.I. Kogan, M.I. Liogon'kii, and V.A. Talanov. The paper is "Range and degree of realizability of formulas in the restricted predicate calculus" [Kibernetika (Kiev) 1969, no.2, 17-28; translation in Cybenetics (Kiev) 5 (1969) 142-154]. I've been told that this paper is rather difficult to read. $\endgroup$ Commented Dec 3, 2012 at 13:58
-
$\begingroup$ Thanks! I actually know this derivation, but I wanted a encapsulated reference to this precise fact. $\endgroup$ Commented Dec 3, 2012 at 14:03