Embedding spanning trees in random graphs
From MaRDI portal
Publication:3013142
DOI10.1137/100805753zbMATH Open1221.05283arXiv1007.2326OpenAlexW2026053156MaRDI QIDQ3013142FDOQ3013142
Authors: Michael Krivelevich 
Publication date: 18 July 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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)}.
Full work available at URL: https://arxiv.org/abs/1007.2326
Recommendations
Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cited In (42)
- Thresholds versus fractional expectation-thresholds
- Packing trees of unbounded degrees in random graphs
- Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
- Random Trees in Random Graphs
- Expanders via Random Spanning Trees
- Spanning structures and universality in sparse hypergraphs
- Local resilience of almost spanning trees in random graphs
- Expanders Are Universal for the Class of All Spanning Trees
- On the performance of randomized embedding of reproduction trees in static networks
- Embedding nearly-spanning bounded degree trees
- A randomized embedding algorithm for trees
- Building spanning trees quickly in maker-breaker games
- Cycle factors and renewal theory
- Fast embedding of spanning trees in biased maker-breaker games
- On the probability that a random subtree is spanning
- An accurate, scalable and verifiable protocol for federated differentially private averaging
- The threshold for combs in random graphs
- The total acquisition number of random graphs
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- Fast strategies in Waiter-Client games
- Edge-disjoint spanning trees and eigenvalues of regular graphs
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
- Spanning trees in random graphs
- Uniform linear embeddings of spatial random graphs
- Almost spanning universality in random graphs
- Fast strategies in maker-breaker games played on random boards
- Spanning trees in graphs without large bipartite holes
- Large bounded degree trees in expanding graphs
- Maximal planar subgraphs of fixed girth in random graphs
- Nonvertex-balanced factors in random graphs
- Optimal threshold for a random graph to be 2-universal
- On the Erdős–Sós conjecture for trees with bounded degree
- Universality of random graphs and rainbow embedding
- Embedding large graphs into a random graph
- A note on universal graphs for spanning trees
- Sharp threshold for the appearance of certain spanning trees in random graphs
- Random perturbation of sparse graphs
- Counting spanning trees in self-similar networks by evaluating determinants
- Expanders are universal for the class of all spanning trees
- Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
- Ramsey goodness of bounded degree trees
- Spanning trees in randomly perturbed graphs
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)
