No label defined (Q3344024)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3878974
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3878974

      Statements

      0 references
      1984
      0 references
      sparse graph
      0 references
      Hamiltonian graph
      0 references
      random graph process
      0 references
      diameter
      0 references
      [For the entire collection see Zbl 0543.00003.] On a set of n nodes a graph process is a sequence (G(0),G(1),...,G(N)) of graphs in which G(t) has t edges and is a subgraph of \(G(t+1)\); here \(N=n(n-1)/2.\) There are N! graph processes on n nodes; by giving them all the same probability we get a random graph process. It is customary to say that almost every graph process has a given property, say Q, if the probability that a random graph process on n nodes has property Q approaches 1 as n tends to infinity. (The unfortunate conflict of this usage with established usage in probability seems by now unavoidable.) The most well-known results in the theory of random graphs are that, as t increases from 0 to N, the graphs G(t) in almost every process acquire large components (of order n rather than log n) at about \(t=n/2\), and they become connected, attain a minimum degree of 2, and become Hamiltonian nearly simultaneously at about \(t=n \log n\). The citations in this paper provide quite a complete bibliography of the subject. This paper and a companion by the same author [The evolution of random graphs Trans. Am. Math. Soc. (to appear)] extend and sharpen several of the existing results. The introduction to this paper amounts to a brief survey of the state of the subject. Section 1 contains the proof of a result used in the companion paper. Section 2 contains the remarkable theorem: Almost every graph process has the property that if T is the smallest index for which G(T) has minimum degree 2, then G(T) is hamiltonian. Section 3 gives upper and lower bounds on the diameter of G(t) for various values of t around the point where G(t) first becomes connected. These bounds, upper and lower, are all of order \((\log n)/(\log \log n).\) Section 4 contains a theorem which can be roughly summarized by saying that very soon after becoming connected, almost every graph process becomes k-connected. Finally, Section 5 deals with an Erdős-problem which the author (perhaps rightly) considers overpriced.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references