Abstract: We prove that if T is a tree on n vertices wih maximum degree D and the edge probability p(n) satisfies: np>c*max{D*logn,n^{epsilon}} for some constant epsilon>0, then with high probability the random graph G(n,p) contains a copy of T. The obtained bound on the edge probability is shown to be essentially tight for D=n^{Theta(1)}.
Recommendations
Cited in
(52)- Maximal planar subgraphs of fixed girth in random graphs
- On the performance of randomized embedding of reproduction trees in static networks
- Thresholds versus fractional expectation-thresholds
- Random perturbation of sparse graphs
- Fast strategies in Waiter-Client games
- Spanning trees in random graphs
- Large bounded degree trees in expanding graphs
- The total acquisition number of random graphs
- Universality of random graphs and rainbow embedding
- Counting spanning trees in self-similar networks by evaluating determinants
- Building spanning trees quickly in maker-breaker games
- Spanning structures and universality in sparse hypergraphs
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Cycle factors and renewal theory
- Local resilience of almost spanning trees in random graphs
- Sharp threshold for the appearance of certain spanning trees in random graphs
- Fast strategies in maker-breaker games played on random boards
- Uniform linear embeddings of spatial random graphs
- Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
- Random Trees in Random Graphs
- Edge-disjoint spanning trees and eigenvalues of regular graphs
- Fast embedding of spanning trees in biased maker-breaker games
- Ramsey goodness of bounded degree trees
- scientific article; zbMATH DE number 747032 (Why is no real title available?)
- Expanders Are Universal for the Class of All Spanning Trees
- Packing trees of unbounded degrees in random graphs
- Nonvertex-balanced factors in random graphs
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Spanning trees in randomly perturbed graphs
- Optimal threshold for a random graph to be 2-universal
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- Embedding large graphs into a random graph
- Expanders via Random Spanning Trees
- A randomized embedding algorithm for trees
- The threshold for combs in random graphs
- Expanders are universal for the class of all spanning trees
- On the Erdős–Sós conjecture for trees with bounded degree
- On the probability that a random subtree is spanning
- Ramsey goodness of trees in random graphs
- An accurate, scalable and verifiable protocol for federated differentially private averaging
- Sharp threshold for embedding balanced spanning trees in random geometric graphs
- Almost spanning universality in random graphs
- Spanning trees in graphs without large bipartite holes
- A note on universal graphs for spanning trees
- Rainbow subgraphs of uniformly coloured randomly perturbed graphs
- Tree universality in positional games
- Creating spanning trees in Waiter-Client games
- Dirac's theorem for linear hypergraphs
- Ramsey numbers of bounded degree trees versus general graphs
- Spanning trees in pseudorandom graphs via sorting networks
- Rainbow spanning trees in uniformly coloured perturbed graphs (extended abstract)
- Embedding nearly-spanning bounded degree trees
This page was built for publication: Embedding spanning trees in random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3013142)
