0
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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...

$\endgroup$
2
4
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Dec 3 '12 at 13:58
  • $\begingroup$ Thanks! I actually know this derivation, but I wanted a encapsulated reference to this precise fact. $\endgroup$ Dec 3 '12 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.