scientific article; zbMATH DE number 3878974
[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.
- Minimal attractors in digraph system models of neuronal networks
- The evolution of the min-min random graph process
- Size and connectivity of the \(k\)-core of a random graph
- Expected parallel time and sequential space complexity of graph and digraph problems
- The number of connected sparsely edged uniform hypergraphs
- On rainbow Hamilton cycles in random hypergraphs
- On offset Hamilton cycles in random hypergraphs
- On the largest component of the random graph at a nearcritical stage
- The average distance and the diameter of dense random regular graphs
- Probabilistic zero forcing on random graphs
- Random graph's Hamiltonicity is strongly tied to its minimum degree
- Spanning trees in random graphs
- Typical and generic ranks in matrix completion
- Hamiltonicity in random graphs is born resilient
- Waiter-client and client-waiter Hamiltonicity games on random graphs
- On resilience of connectivity in the evolution of random graphs
- A hierarchy of randomness for graphs
- Rainbow arborescence in random digraphs
- On the path separation number of graphs
- Packing Hamilton cycles online
- A counting lemma for sparse pseudorandom hypergraphs
- Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
- Perfect matchings and Hamiltonian cycles in the preferential attachment model
- Optimal covers with Hamilton cycles in random graphs
- scientific article; zbMATH DE number 861324 (Why is no real title available?)
- The threshold for the square of a Hamilton cycle
- Dirac's theorem for random regular graphs
- Hamiltonian Berge cycles in random hypergraphs
- Finding tight Hamilton cycles in random hypergraphs faster
- Maker-Breaker games on randomly perturbed graphs
- Crux and Long Cycles in Graphs
- Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
- Hamiltonian cycles and subsets of discounted occupational measures
- Finding a Hamilton cycle fast on average using rotations and extensions
- Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs
- Birth of a giant \((k_{1},k_{2})\)-core in the random digraph
- Recent advances in percolation theory and its applications
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- Evolving Graph-Structures and Their Implicit Computational Complexity
- Counting connected hypergraphs via the probabilistic method
- Manipulative waiters with probabilistic intuition
- The threshold probability for long cycles
- On covering expander graphs by Hamilton cycles
- Hamiltonicity of random graphs produced by 2‐processes
- The isoperimetric constant of the random graph process
- A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
- On the probability of planarity of a random graph near the critical point
- Hamilton cycles in random geometric graphs
- Expanders are universal for the class of all spanning trees
- The stripping process can be slow. II
- The chromatic number of random graphs
- The diameter of sparse random graphs
- Singularity of the \(k\)-core of a random graph
- Evolving Shelah‐Spencer graphs
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Perfect matchings in random subgraphs of regular bipartite graphs
- The global resilience of Hamiltonicity in \(G(n, p)\)
- Cycle lengths in randomly perturbed graphs
- ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs
- Hamilton completion and the path cover number of sparse random graphs
- Multistage positional games
- Component behaviour and excess of random bipartite graphs near the critical point
- Hamilton cycles in the line graph of a random hypergraph
- D-chain tomography of networks: a new structure spectrum and an application to the SIR process
- A branching process with deletions and mergers that matches the threshold for hypercube percolation
- Resilience for tight Hamiltonicity
- Resilience with respect to Hamiltonicity in random graphs
- Spanning cycles in random directed graphs
- Hamilton cycles in pseudorandom graphs
- Nearly Hamilton cycles in sublinear expanders and applications
- Fast construction on a restricted budget
- Hamiltonicity of sparse pseudorandom graphs
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Building graphs with high minimum degree on a budget
- The completion numbers of Hamiltonicity and pancyclicity in random graphs
- Hamilton cycles in pseudorandom graphs (extended abstract)
- Constructing Hamilton cycles and perfect matchings efficiently (extended abstract)
- The k-core in percolated dense graph sequences
- Hamilton cycles and perfect matchings in the KPKVB model
- Hamiltonicity of random subgraphs of the hypercube
- On the chromatic number of random triangle-free graphs
- Survival probabilities for N-ary subtrees on a Galton-Watson family tree
- Connectivity of inhomogeneous random graphs. II
- On the robustness of random k-cores
- Counting connected graphs asymptotically
- Survival time of a random graph
- Asymptotic normality of the \(k\)-core in random graphs
- On two Hamilton cycle problems in random graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3344024)