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
1984
0 references
sparse graph
0 references
Hamiltonian graph
0 references
random graph process
0 references
diameter
0 references
0.8094503283500671
0 references
0.8030531406402588
0 references
0.8023185729980469
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